The Gateway to Computer Science Excellence
0 votes
109 views
$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 (331 points)
edited by | 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

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

by Active (1.1k points)

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
50,644 questions
56,523 answers
195,611 comments
101,287 users