Question

Consider the language $\mathit{F}\mathbf{=}\mathbf{\{}\mathbf{}{\mathit{a}}^{\mathbf{i}}\mathbf{,}{\mathit{b}}^{\mathbf{j}}\mathbf{,}{\mathit{c}}^{\mathbf{k}}\mathbf{⩾}\mathbf{0}\mathit{a}\mathit{n}\mathit{d}\mathit{i}\mathit{f}\mathit{i}\mathbf{=}\mathbf{1}\mathit{t}\mathit{h}\mathit{e}\mathit{n}\mathit{j}\mathbf{=}\mathit{k}\mathbf{\}}\mathbf{.}$

a. Show that F is not regular.

b. Show that F acts like a regular language in the pumping lemma. In other words, give a pumping length and demonstrate that F satisfies the three conditions of the pumping lemma for this value of P.

c. Explain why parts $\left(a\right)\mathit{a}\mathit{n}\mathit{d}\left(b\right)$do not contradict the pumping lemma.

Short answer

1. It is proved that the language is not regular.
2. It is shown that F acts like regular language in pumping lemma.
3. Part $\left(a\right)and\left(b\right)$don’t contradict the pumping lemma.

Step-by-step solution

Step 1: Define Pumping lemma

The pumping lemma says that for any string in the language, with length greater than the pumping length, we can write $s=xyzwith\left|xy\right|⩽p,$such that $x{y}^{i}z$is also in the language for every $i⩾0$.

Prove that F is not regular

(a)

We claim all strings of the form $a{b}^i$must be in distinct equivalence classes for all $i⩾0$. This is because any two strings $a{b^i}_{1}anda{b^i}_2$can be distinguished by ${c^i}_1$, since$a{b^i}_1{c^i}_1\in F,whilea{b^i}_2{c^i}_1\notin F$ . Since there are infinitely many equivalence classes of the indistinguishability relation, we conclude by the Myhill-Nerode theorem that no DFA can recognize F .

Show acts like regular language in pumping lemma.

(b)

For the given language, we can take $p=2$. Consider any string $a^i{b}^j{c}^k$in the language. If $i=1ori>2$, we take $x=aandy=a.Ifi=1,$we must have $j=k$and adding any number of a’s still preserves the membership in the language. For $i⩾2$, all strings obtained by pumping y as defined above, have two or more a’s and hence are always in the language.

For$i=2$, we can take $x=\in andy=a$. Since the strings obtained by pumping in this case always have an even number of a ’s, they are all in the language.

Finally, for the case $i=0$, we take$x=\in andy=b$ if$j>0andy=c$ otherwise. Since strings of the form $b^j{c}^k$are always in the language, we satisfy the conditions of the pumping lemma in this case as well.

Show that part aandbdon’t contradict pumping lemma

(c)

The pumping lemma simply states that if a language is regular, it must satisfy the lemma's criteria. However, this does not imply that no non-regular language may meet these requirements.