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)^*$
in Theory of Computation by
edited by | 131 views
$L_{1}^{2} = {a^{p}b^{p}a^{q}b^q \mid p,q\geq 0}$

do you think this is regular?
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.
MK Utkarsh.. i think it should be $a^{p}$$b^{p}$$a^{p}$$b^{p}$... so on.
tarun why same powers? it will be $a^{p}b^{p}a^{q}b^{q}a^{r}b^{r}....$ and so on
First L1 is not Regular because here comparison is needed to check equality b/w  a and b. its  Kleene star L2 also not be regular .

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.

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

i thought every n can be different for each L

1 Answer

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


Related questions

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
52,345 questions
60,516 answers
95,366 users