Correct labeling for this regular language?

Question

So I am a newbie computer science person and would like some help from the community in helping me understand this subject.

I have this regular language I am trying to determine is 3 things from this language: DOUBLE = {w | w contains twice as many 0s as 1s}

• NOT regular
• context-free
• decidable

My thinking for each is that

it's not regular because of the Pumping Lemma. Assume for the sake of contradiction, that DOUBLE is regular. If we were to use string \(0^n1^n\) then for the three conditions.

1. |xy| ≤ n
2. |y| > 0
3. For all integers i ≥ 0, the string xy^iz is also in L. When applied the Pumping Lemma doesn't not work

is context free because if we use a context-free grammar (CFG) that look like S -> 0S1S | ε generates strings that have twice as many 0s as 1s

is decidable because it contains twice as many 0s as 1s

Answer 1

• NOT regular for the reason you said
• NOT context free (test your try with this tool, you'll find that it also matches "01" which does not have twice the 0s than 1s). In general, Context-free grammars are not capable of "counting" indefinitely, you'll need a push-down automata for that
• IS decidable because you can easily code an algorithm to accept/reject a string, by counting the digits

Answer 2

Language is not Regular

The language is not regular which can be showed via the pumping lemma for regular languages. In your proof you should have used a string that actually is in the language e.g.: w = xyz = 0^(2p) 1^(p). As using a string that is already not part of the language, would provide little information about the conclusions of the pumping lemma.

Then given the pumping lemma:

• w = xyz = 0^(2p) 1^(p)
• |xy| <= p
• |y| >= 1
• q = xy^(i) z, q is in the language for all i.

As |xy| <= p, the substring |xy| exists of only zeroes. As |y| > 1, there is at least one zero in y, and at most p zeroes in y.

If we pumped y, then that would mean that the output string is of the form: #w(0) = #y(0) * i + #x(0) + p

The language asserts:

• #w(0) = 2#w(1)
• #y(0) * i + #x(0) + p = 2p
• #y(0) * i + #x(0) = p

As we can pump i forever, we can always reach an inequality. Showing that there is no valid derivation among xyz, thus the pumping lemma for regular languages is not applicable, thus the language is not regular.

Language is Context-Free

The language is a context-free language, however, not by the grammar you have specified. The right context-free grammar for this language is:

S -> S0S0S1S
   | S0S1S0S
   | S1S0S0S
   | ε 

Essentially, whenever a '1' is added we must ensure that 2 zeroes are added, the order is irrelevant, but they must be placed. Due to this assertion, we can recursively assume that for each '1' there are 2 zeroes. Which follows the 'w contains twice as many zeroes than ones'.

Language is Context-Sensitive, Decidable, or other language class

Showing that the language is context-sensitive, or some other complexity class is trivial. As we already showed that it is context-free, all language classes that contains the context-free language class as a subset also accepts this language.

Examples of language classes that have the context-free language class as subset:

• Context-Sensitive
• Recursive Enumerable
• Decidable