@https://gateoverflow.in/user/Kushagra+Chatterjee

L* contains Language L which is not prime. So How can you say that L* is regular?

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

0 votes

`L = {a^n: n ≥ 2, is a prime number}.`

`This is not a regular language.`

`What about L*?`

`Is it regular? Please explain.`

+1 vote

Let ∑ = {a} and L_{1} = ∑*

Then we can say that L_{1} is regular.

Now take any arbitrary string x belongs to ∑*

then x = a^{m} for some integer m

Now, m must have a prime factor p

Hence m = p*k (for some integer k)

Hence, a^{m} = a^{p} . a^{p} . a^{p} . a^{p} .....(concatenating the string a^{p} k times)

Now, a^{p} belongs to L (given in the question ) which means (a^{p })^{k } belongs to L*

Hence a^{m} belongs to L* which means x belongs to L*

So, for any arbitrary string x belongs to ∑* we get that x belongs to L*

Hence ∑* = L*

Thus L* is a regular language.

0

@https://gateoverflow.in/user/Kushagra+Chatterjee

L* contains Language L which is not prime. So How can you say that L* is regular?

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.3k
- Algorithms 3.7k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.4k
- CO & Architecture 2.9k
- Computer Networks 3.4k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 482
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,903 questions

47,560 answers

146,294 comments

62,306 users