Decide if L is regular or not and argue it. Trying to use Pumping Lemma

Question

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.

Answer 1

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.

Answer 2

(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.

Answer 3

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.