Question

Question 1
a) Determine whether the language {a n b m c n | n > 0} is regular or not using pumping Lemma.


b) Prove that the language
{(ai bn | i, n > 0, i = n or i = 2n} is not regular using the Pumping
Lemma.

Answer 1

For this question we can say that to solve this question we need to understand pumping lemma.

PUMPING LEMMA:

pumping lemma basically is used to prove that any provided language is regular or not.

now pumping lemma can be stated for every regular Language(if it is regular) L,there exist an integer /constant "C" such that for every string J in L will be |J| C (|x| means length of x)

we can deduce J into 3 strings

J=XYZ,such that

• |Y| > 0
• |XY|C
• and last condition for all K0, string is also belongs to language L.

now comming to question:

part1.)the given language is

now we can take J as and let c=n where n is the number of states

now proving the three parts of lemma:

• 
• now J can be represented as J=XYZ where X=,Y=,and Z=
• |Y|>0,if m0
• now |XY|C
• and let us take n=3 and k=m=2
• which is,aaabbccc which belongs to the language L
• hence proved language L is regular language

part 2.)

given language is

now we can represent this language as :

• let J= .and this implies
• by pummping lemma,let J=XYZ, where |XY| n
• now let ,where n>0 .hence |Y|0
• let us take K=3 , then our string will be =,which is not a part of language L
• and thus this proves that language L is not regular.