Lets say we have $L_1$ which contains all binary numbers divisivle by 2 but not by 4. I would say this language contains all words with a 10 at the end. Ive found a regular grammar $G$ with $L(G) = L_1$ so that $L_1$ must be regular.

Now I have the problem that my teacher told me that $L_2 = \{ww| w \in \{0,1\}*$ and $w$ ends with 10$\}$ is not context free.

But if $L_1$ is regular or context-free, so should $L_1L_1=L_2$ be also regular and context free.

Where is the mistake?

  • $\begingroup$ Let's say $G$ is a grammar for a regular language $L_1$. Can you use it to make a regular grammar for $L_1.L_1$? If you start with $S_0\rightarrow GG$ you may accept some words which do not belong to $L_1.L_1$. Neither regular Grammars not Context-Free Grammars are not able to determine $ww$ for $w\in\{0,1\}^*$. $\endgroup$ – Doralisa Aug 4 '18 at 12:37

There is a difference between $L_2 = \{ww\mid w \in L_1\}$ and $L_3 = L_1 L_1$. $L_3$ is $\{wx\mid w, x \in L_1\}$; in, other words all strings consisting of two sentences from $L_1$, which is regular / context-free if $L_1$ is regular / context-free.

$L_2$ is the set of all strings consisting of one repeated string from $L_1$, which is not in general context-free. (It is regular if $L_1$ is finite or is a regular language over a singleton alphabet. But your example does not fall into either of these categories.)

| cite | improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.