@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.3k
- Engineering Mathematics 5.4k
- Digital Logic 2.1k
- Programming & DS 3.9k
- Algorithms 3.4k
- Theory of Computation 4.2k
- Compiler Design 1.6k
- Databases 3.1k
- CO & Architecture 2.7k
- Computer Networks 3.1k
- Non GATE 1.1k
- Others 1.4k
- Admissions 501
- Exam Queries 448
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

37,963 questions

45,466 answers

131,323 comments

48,379 users