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

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

$L_2 = (L_1)^*$

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

do you think this is regular?
0
i used the following approach

using pumping lemma for regular languages

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.
+1
MK Utkarsh.. i think it should be $a^{p}$$b^{p}$$a^{p}$$b^{p}$... so on.
0
tarun why same powers? it will be $a^{p}b^{p}a^{q}b^{q}a^{r}b^{r}....$ and so on
0
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

Utkarsh see there is difference.. keen star is repetition of the string(same for all) for zero or more time... that is different from L3 in that link.

+1
keen star is repetition of the string ok
but what is kleen star over a language?
+2
ok ok.. if it would have been ( a$^{n}b^{n}$)* then what i said would be true?
0
yeah you're right thanks

i thought every n can be different for each L

+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.

by Active (1.1k points)