2
$\begingroup$

$S -> AB$

$A -> aA / epsilon$

$B ->aBb / epsilon$

What is the class of language generated by the above grammar ?

I think that it generates $a^* a^n b^n | n>=0$ so it should be regular as regular is concatenated with DCFL which is able generate epsilon. But the answer is CFL .

I think that answer would be CFL if n would have been greater than equal to 1 and not 0

Can someone please point out my mistake ?

$\endgroup$
12
  • $\begingroup$ It seems that $L = \{ a^* a^n b^n \} = \{ a^m b^n \mid m \geq n \}$ which is .... In other words the implication $R \in Reg, C \in CFL, \epsilon \in C \Rightarrow R \cdot C \in Reg$ is wrong. You cannot say that if $C$ can generate $\epsilon$ then $R \cdot C \in Reg$; you must consider ALL strings that can be generated both by $R$ and $C$. $\endgroup$ – Vor Oct 24 '17 at 19:35
  • $\begingroup$ This answer also uses similar logic to prove that language is regular math.stackexchange.com/q/649335/403592. I am not understanding the difference between n>=0 and n>=1. How will that change the answer ? @Vor. $\endgroup$ – Rajesh R Oct 24 '17 at 19:35
  • $\begingroup$ Here is one more link which says L1.L2 is regular if L1 is regular and L2 is non regular containing epsilon. math.stackexchange.com/questions/1298201/… $\endgroup$ – Rajesh R Oct 24 '17 at 19:39
  • $\begingroup$ Read both questions carefully ... they doesn't prove what you say. For example in the first question they assume that $B = \Sigma^*$, in the second question they assume that $L_1 = \Sigma^*$. And in the third case they use $L_1 = \{a^m b^n \mid m \neq n$ which, if prefixed with $a^*$, can generate $\Sigma^*$ which is regular. $\endgroup$ – Vor Oct 24 '17 at 19:44
  • 1
    $\begingroup$ Yes!!! (mmmm probably not DCFL, but surely CFL and surely not regular) $\endgroup$ – Vor Oct 24 '17 at 20:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.