The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

0

@Deepakk Poonia (Dee) please reply....i have one more doubt.... pumping lemma is used to prove non regularity of language but if a language satisfies pumping lemma then it may or may not be regular...right?

if it is so then i am not able to understand ur assumption!

0

is this language CFL?

Yes. This 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 \} $

0

if a language satisfies pumping lemma then it may or may not be regular...right?

if it is so then i am not able to understand ur assumption!

Yes. If a language satisfies pumping lemma then it may or may not be regular.

$L\,\, is\,\, Regular\,\, \rightarrow \,\,L\,\, satisfies\,\, Pumping \,\,lemma$

Contrapositive also True for Every Implication statement, So,

$\,\, \,\,L\,\, does\, not\,\, satisfy\,\, Pumping \,\,lemma \rightarrow L\,\, is\,\, Non-Regular$

I assumed $L$ is Regular, So, It must satisfy Pumping lemma. But it didn't satisfy it, So, My assumption that $L$ was Regular,was false.

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.7k
- Digital Logic 2.2k
- Programming & DS 4.1k
- Algorithms 3.6k
- Theory of Computation 4.5k
- Compiler Design 1.7k
- Databases 3.2k
- CO & Architecture 2.8k
- Computer Networks 3.2k
- Non GATE 1.1k
- Others 1.5k
- Admissions 503
- Exam Queries 474
- Tier 1 Placement Questions 22
- Job Queries 61
- Projects 13

39,751 questions

46,767 answers

140,662 comments

58,537 users