Peter Linz Exercise 4.3

Question

Show that the language

$$\begin{align*} L = \left \{ a^nb^{n+k} \;\; : n\geq 0,k\geq 1 \right \} \cup \left \{ a^{n+k}b^{n} \;\; : n\geq 0,k\geq 3 \right \} \end{align*}$$

is not Regular.

Answer 1

If I take k=1 in a^(n)b^(n+k) then it will become a^(n)b^(n+1) i.e. for every a i need one extra b.This requires comparison and thus requires stack.So we cannot make a DFA fo this and thus not regular.

Answer 2

For both parts of the given statement, both of them are irregular. And both of them cannot be expressed by a DFA as both need memory to remember the number of a's (in first one) and number of b's(in second one). Hence, an union operation between the two will also produce an irregular language.

Comments

not the correct way to prove such questions and also Union of 2 non-regular languages can be regular

Answer 3

\begin{align*} L = \left \{ a^nb^{n+k} \;\; : n\geq 0,k\geq 1 \right \} \cup \left \{ a^{n+k}b^{n} \;\; : n\geq 0,k\geq 3 \right \} \end{align*}

Assuming L is regular.  Let $m$ be the pumping length given by the pumping lemma.

We pick our string , $w =$ $a^n b^{2n}$ , when $n=k$ and $n,k \geq 3$ 

then $w \in L$ must be true,

for $|w|>m$ assume n = m,

$w =$ $a^m b^{2m}$ ,

Then from the pumping lemma there exists $x, y, z \in Σ^{∗}$ such that w = xyz , |xy| ≤ m and |y| ≥ 1.

$w_{i} = xy^{i}z$ 

 y must contain entirely of a's 

 suppose $|y|=k$ and  $1 \leq k \leq m$,

then $|xy^{1}z|$ = $a^{m}a^{k}b^{2m}$ 

if  $k = m$ and $i = 1,$ 

= $|xy^{1}z|$ = $a^{2m}b^{2m}$  

This shows that $n_{a} = n_{b}$ but no such string exists in L because in L either $n_{a} > n_{b}$ or $n_{a} < n_{b}$.

This indicates that the assumption that L is regular must be false. 

     Hence L is not regular