MadeEasy Test Series: Theory Of Computation - Regular Languages

Question

Which of the following is Regular?

Comments

I think both are regular.What's the answer given?

---

Yes, both are Regular. There is no doubt with S2. But S1 is a bit confusing. Can you explain

---

it will produce a* i think

---

No idea

---

try taking examples.take value of m and n and see

---

S1 is string with any number of a's as you can represent any string of a in term of (a^n)^m where m is greater or equal than n.

---

How  2nd regular

Answer 1

S1. (a^n)^m can be written as (x)^m , m>=0 , which is regular.

S2. {a^nb^n / n>=1} it is CFL  U  {a^nb^m /n,m>=1} - it is regular.

So CFL U REG = REG and if it is regular then it will be CFL also.

Comments

yeah, got it thanks

---

Explanation of the second one is not correct I guess.

• For CFL and DCFL union with Regular language is closed.
  • CFL U RL = CFL

---

@Dhillu Yes correct