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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,644 questions

56,523 answers

195,611 comments

101,287 users