The Gateway to Computer Science Excellence
0 votes
111 views

Which of the following is Regular?

in Theory of Computation by Active (4.6k points)
edited by | 111 views
0
I think both are regular.What's the answer given?
0
Yes, both are Regular. There is no doubt with S2. But S1 is a bit confusing. Can you explain
0
it will produce a* i think
0
No idea
0
try taking examples.take value of m and n and see
0
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.
0
How  2nd regular

1 Answer

0 votes
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.
by Active (1.7k points)
0
yeah, got it thanks
0

Explanation of the second one is not correct I guess.

  • For CFL and DCFL union with Regular language is closed.
    • CFL U RL = CFL
0
@Dhillu Yes correct
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,666 questions
56,168 answers
193,841 comments
94,047 users