484 views
0 votes
0 votes

 L = {anbk : | n – k | = 2}

L is regular or not?Please provide explanation

2 Answers

0 votes
0 votes
It should be non regular.
edited by
0 votes
0 votes

If you seek Formal Proof then here it goes. We will use Pumping lemma for regular languages to Prove that It is Not Regular.


Pumping lemma for Regular languages says

" If A languages is Regular,

then $\exists P \geq 1$, such that 

$\forall \,\,strings\,\,w \in L$, Where $|w| \geq P$

$\exists x,y,z$, such that $w = xyz$

and $|xy| \leq P$

and $y \neq \in$ i.e. $|y| \geq 1$

and $\forall q \geq 0$, $xy^qz \in L$


In Words, If $L$ is regular, then there’s some magic number $P$(Called Pumping length). And if I take any string $w$ that is at least as long $P$, then I can break it up into three parts $x, y, $and $z.$ Now, the length of $xy$ is less than or equal to $P$, and also the length of $y$ is greater than or equal to $1$ and less than or equal to $P$.


NOTE that The first line is If $L$ is regular This means that our theorem only applies if the language is regular. It doesn’t apply if $L$ is not regular. I know you don't agree. But hold on. I'll prove it to you.  

People say that We use the pumping theorem to show that a language isn’t regular. And It is indeed True. Then Why did I say the above line??

That's because Pumping lemma is a Proof by Contradiction. In other words, we assume $L$ is regular, then we show that it doesn’t satisfy the pumping theorem. This gives us a contradiction, so our initial assumption that $L$ is regular must be wrong.


So, Now let's consider the given language $L = \left \{ a^nb^k, |n-k| = 2 \right \}$

Let's Assume that $L$ is Regular.  

Now, Since we have assumed that $L$ is Regular, so, This means that there’s some ”magic number” $P$ for the language $L$, such that the all the things in the rest of the theorem are true. 

So, Let's take Pumping length as $P$ and now, Every String of length $\geq P$ must satisfy the rest of the conditions of the Pumping lemma. 

So, as Pumping lemma states, For all $w$, where $|w| \geq P$, i.e. Sufficiently Large Strings, $w$ can be split into three Parts $x,y,z$.

So, Let's take some sufficiently large string with $|w| \geq P$ (as All the Strings with length greater than or equal to $P$ must satisfy the condition..)

So, Let $w = a^pb^{p-2}$ . Now let's try to split $w$ in three parts $x,y,z$ such that $|xy| \leq P$, $y \neq \in$

Now, $y$ has to be in the part $a^p$ because $|xy| \leq P $ and $|y| \geq 1$. You can try taking $y$ from $a$ to $a^P$ but You can find that $xy^qz$, $\exists q \geq 0$, Will Not be in the language. 

So, We have shown that $L$ does not Satisfy the conditions of Pumping lemma. So, Our assumption that $L$ is Regular, was wrong. Hence, $L$ is Not regular.


$L$ is CFL. You can write it as Union of Two CFL languages as follows :

$\left \{a^nb^k:|n-k| = 2 \right \} = $ $\left \{a^nb^k:n-k = 2 \right \} $ $\cup \left \{a^nb^k:k-n = 2 \right \} $

You can find one more detailed explanation for another Non-regular language using Pumping lemma here in my answer : : https://gateoverflow.in/146637/prove-a-language-is-regular-using-pumping-lemma 

edited by

Related questions

0 votes
0 votes
0 answers
1
0 votes
0 votes
1 answer
2
himgta asked Jul 14, 2018
234 views
0 votes
0 votes
1 answer
3
himgta asked Jul 14, 2018
253 views
1 votes
1 votes
2 answers
4
himgta asked Jul 4, 2018
444 views