4,113 views
1 votes
1 votes
Let P,Q,R be 3 languages. If P and R are regular and if PQ=R, then

a)Q has to be regular

b)Q can not  be regular

c)Q need not  be regular

d)Q has to be CFL

1 Answer

Best answer
4 votes
4 votes
P : Regular

R : Regular

P.Q = R

Option B can directly eliminated : Q can be regular because if we concatenate two regular languages than their result is regular.

Option D can also eliminated : Q need not be CFL , it can be regular also.

option A can be eliminated :if we take Q as CFL. for eg: P : $\phi$    Q: $a^nb^n$  then R = $\phi$  which is regular.

So option C is best
edited by

Related questions

6 votes
6 votes
4 answers
4
ari asked Aug 18, 2015
2,964 views
Let $A$ and $B$ be disjoint, R.E. languages. Let $\bar A \cup \bar B$ also be recursive enumerable. What can you say about $A$ and $B$?(a) Neither A nor B is decidable is...