1
$\begingroup$

I'm having today a test on formal language theory, and I've seen a question about it I'm having hard time solving. The question is: Give an example of 2 languages, L,M which are non-context-free but LM(the concatenation) is a context-free language but not a regular language. Thanks in advance

$\endgroup$

1 Answer 1

0
$\begingroup$

Let $1$ denote the empty word. Let $$ S = \{a^nb^n \mid n \geqslant 0\},\quad T= 1 + \{c^{2^n}\mid n \geqslant 0\},\quad L = ST,\quad M = 1 + (c^* - T). $$ Observe that $$c^* = T \cup M \subseteq (1+T)(1 + M) = TM$$ and hence $TM = c^*$. Now the languages $L$ and $M$ are not context-free but $LM = Sc^*$ is context-free but not regular.

$\endgroup$
2
  • $\begingroup$ What is the meaning $1 + (c^* - T)$ and so on? $\endgroup$
    – vonbrand
    Feb 11, 2020 at 18:09
  • $\begingroup$ $+$ denotes union and $-$ set difference. $\endgroup$
    – J.-E. Pin
    Feb 11, 2020 at 18:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .