Part (a): Let $L = \{x \in \{0,1\}^* \mid \#0(x) \neq 4\times\#1(x)\}$, where $\#0(x)$ means the number of 0 in string $x$ and $\#1(x)$ means the number of 1 in string $x$.

So I want to use the pumping lemma. But I'm having a hard time choosing a string so that I can show that it is not regular.

I've been thinking about how I could use something like the string, s, = $0^{3p}1^p$. But I do not see how you use that fact (I would like to show that xyyz would equal $0^{4p}1^p$). This route seems unfruitful. So any help would be nice.

Part (b): Let $L = \{x \in \{0,1\}^* \mid \exists k \in \mathbb{N}, \#0(x) + \#1(x) = 2k\}$.

Again stuck on this problem. My original approach was to leverage the fact that the parity is the same on the 0s and 1s (if one is even, then so does the other and vice versa. Same for odd parity.)

Again, this does not seem to be working.


For part (a), if you are intent on using the pumping lemma, then you can either use Subhayan's suggestion and first complement the language, or just do it directly like so. Let $p$ be the constant promised by the pumping lemma, and consider the following word: $$ w = 1^p 0^{4(p!+p)} \in L. $$ According to the pumping lemma, you can write this as $w = xyz$ with $|xy| \leq p$ and $|y| \geq 1$, so that $y = 1^k$ for some $1 \leq k \leq p$. Furthermore, the pumping lemma guarantees that $xy^iz \in L$ for every $i \geq 0$. Now take $i = (p!/k)+1$. Then $$xy^iz = 1^{p-k}1^{k(p!/k)+1} 0^{4(p!+p)} = 1^{p!+p} 0^{4(p!+p)} \notin L.$$

Another option is to use the Myhill-Nerode criterion; it then makes no difference whether or not you complement $L$. For some reason this criterion isn't usually taught in introductory classes. The idea is to consider some DFA accepting $L$. If two words $x,y$ end up at the same state of the DFA, then for every word $z$, $xz \in L$ iff $yz \in L$. In particular, if two words $x,y$ don't satisfy this condition (we say that they conflict), then they must end up at different states of the DFA. Hence we find an infinite number of pairwise conflicting words, $L$ isn't regular.

Such an infinite sequence of pairwise conflicting words is $x_n = 1^n$. Indeed, given $n \neq m$, consider $z_n = 0^{4n}$. We have $x_n z_n \notin L$ but $x_m z_n \in L$, and so $x_n$ and $x_m$ conflict.

For part (b), $L$ is just the language of all words of even length. Hence we can improve on Subhayan's answer by designing a DFA for $L$ using only two states.

  • $\begingroup$ Is there any insight that made you use the w that you did? $\endgroup$ – user678392 Sep 7 '13 at 19:43
  • $\begingroup$ The idea of using factorial exponents appears in proofs of inherent ambiguity of context-free languages, for similar reasons - you want to guarantee being able to pump to an exact length no matter what the length of the pumped part is. $\endgroup$ – Yuval Filmus Sep 7 '13 at 20:10

(a): Recall that regular languages are closed under complement, i.e if $L$ is regular, so is $L'$. ($F_{L'} = Q_L- F_L$)

Assume that $L$ is regular. This follows: if $L = \{x \in \{0,1\}^* \mid |x|_0 \neq 4.|x|_1 \}$ is regular, then so is $L' = \{x \in \{0,1\}^* \mid |x|_0 = 4.|x|_1\} $

Now you should show that $L'$ is not regular. And that gives you a contradiction.

(b) You can construct the following DFA for this. enter image description here


For part (a), instead of doing everything and go back to pumping lemma, you can try to use a famous nonregular language, which is $K=\{x: \#0(x)=\#1(x)\}$. You probably saw this language already, and a proof of $K$ being nonregular is classic and easy to find.

Now you want to deduce from that that $L$ is nonregular, which is the same as showing that its complement $L'$ is nonregular. For this you can use the fact that regular languages are closed under inverse images of morphism.

We look at the morphism $\varphi:\{0,1\}^*\to\{0,1\}^*$ defined by $\varphi(0)=0000$ and $\varphi(1)=1$. Remark that $K=\varphi^{-1}(L')$. If $L'$ was regular, then $K$ would also be, which we know is not the case. Therefore $L'$ is nonregular, and its complement $L$ too.

For part (b), as Yuval Filmus said you are just accepting words of even length, so a 2-states automaton is a witness that your language is regular.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.