$L_{1}^{2} = {a^{p}b^{p}a^{q}b^q \mid p,q\geq 0}$

do you think this is regular?

do you think this is regular?

The Gateway to Computer Science Excellence

0 votes

$L2$ is Regular ot not.?Please give proper example.

$L_1= \{a^nb^n \mid n\geq 0 \} $

$L_2 = (L_1)^*$

$L_1= \{a^nb^n \mid n\geq 0 \} $

$L_2 = (L_1)^*$

0

i used the following approach

using pumping lemma for regular languages

proof by contradiction

let L2 be a regular language and let pumming lengh be P

let choose the string (a)^p(b)^p

now this problem boils down to proving a^nb^n not regular

correct me if I'm wrong.

using pumping lemma for regular languages

proof by contradiction

let L2 be a regular language and let pumming lengh be P

let choose the string (a)^p(b)^p

now this problem boils down to proving a^nb^n not regular

correct me if I'm wrong.

0

First L1 is not Regular because here comparison is needed to check equality b/w a and b. .....so its Kleene star L2 also not be regular .

+1 vote

Basic: A language is not regular Language if you need an extra Data structure for keeping track of alphabet.

Here the same problem:

In L1, we need to keep track of **'a' **so that you can compare with a number of **'b'**. So L1 is not regular Language.

Similarly, in L2 = { a^nb^n, a^nb^na^nb^n, ............}. here we also need to compare a number of 'a' and 'b'. So, L2 is also not a regular language.

If anything not clear, please comment, I try to simplify more.

52,345 questions

60,516 answers

201,936 comments

95,366 users