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.
Asked By : user678392
Answered By : Yuval Filmus
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/14180
0 comments:
Post a Comment
Let us know your responses and feedback