The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
60 views

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

L is regular or not?Please provide explanation

asked in Theory of Computation by Active (2.8k points) | 60 views

2 Answers

0 votes
It should be non regular.
answered by Boss (24.3k points)
edited by
0
No. It isn't Regular. As strings like $a^{100}b^{98} \in L$, But  FA cannot do this comparison.
0
Yes , there is infinite string is possible
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 

answered by Boss (20.7k points)
edited by
0
is this language CFL?
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.

Related questions

0 votes
1 answer
2
asked Jul 14 in Theory of Computation by himgta Active (2.8k points) | 30 views
0 votes
1 answer
3
asked Jul 14 in Theory of Computation by himgta Active (2.8k points) | 31 views
+1 vote
2 answers
4
asked Jul 4 in Theory of Computation by himgta Active (2.8k points) | 46 views
+1 vote
0 answers
5
0 votes
1 answer
6
+1 vote
1 answer
7
asked Jul 13 in Theory of Computation by himgta Active (2.8k points) | 46 views


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,240 questions
49,722 answers
163,928 comments
65,837 users