# concatenation of regular and DCFL

$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 ?

• 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$. – Vor Oct 24 '17 at 19:35
• 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. – Rajesh R Oct 24 '17 at 19:35
• 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/… – Rajesh R Oct 24 '17 at 19:39
• 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. – Vor Oct 24 '17 at 19:44
• Yes!!! (mmmm probably not DCFL, but surely CFL and surely not regular) – Vor Oct 24 '17 at 20:13