0
$\begingroup$

Let $L$ be the language generated by a context-free grammar whose start variable is $S$. Does adding $S \rightarrow SS$ in this grammar creating language $L^*$, why? What about grammars in Chomsky normal form?

$\endgroup$
  • 1
    $\begingroup$ Welcome to Computer Science! What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael Jun 13 '18 at 20:31
  • 1
    $\begingroup$ Mind the empty word. $\endgroup$ – chi Jun 14 '18 at 12:46
6
$\begingroup$

As chi pointed out in the comment, since $\varepsilon\in L^*$ and $\varepsilon$ may not belong to the new grammar, so adding $S\rightarrow SS$ does not always generate $L^*$. It makes more sense to ask whether it generates $L^+$, so the following answer focuses on $L^+$.


General Form

Consider the following grammar:

\begin{align} S&\rightarrow aSb\\ S&\rightarrow \varepsilon \end{align}

It generates the language $L=\{a^nb^n\mid n\in\mathbb{N}\}$.

Now after adding $S\rightarrow SS$ in this grammar, the string $aababb$ can be generated by the grammar but it does not belong to $L^+$.

Chomsky Normal Form

Easy to see $L^+$ can be generated by the new grammar. Now for any string $s$ generated by the new grammar, we can prove $s\in L^+$ by mathematical induction on the depth of its parse tree. Consider the derivation process of $s$.

If the first derivation does not use the rule $S\rightarrow SS$, we can conclude $S$ does not show up in the following derivation since $S$ does not show up in the right hand side of a CFG of Chomsky normal form. As a result, $s\in L$.

If the first derivation uses the rule $S\rightarrow SS$, the strings generated respectively by the two $S$'s in the right hand side must belong to $L^+$ due to inductive assumption, thus $s$, which is formed by concatenating the two strings, also belongs to $L^+$.

$\endgroup$
  • 1
    $\begingroup$ The last proof only proves that $L(G \cup \{S\to SS\}) \subseteq L(G)^*$. The converse inclusion looks false, in general, e.g. when $G=\{S\to a\}$. $\endgroup$ – chi Jun 15 '18 at 12:55
  • $\begingroup$ @chi Isn't $L(G)^*=\{a\}^*\subseteq L(\{S\rightarrow SS, S\rightarrow a\})$? $\endgroup$ – xskxzr Jun 15 '18 at 13:12
  • 1
    $\begingroup$ No, since $\{a\}^* \not\subseteq \{a\}^+$. I think the only issue here is the empty word, and that using $L^+$ instead of $L^*$ should fix everything. So, I'm being a bit pedantic here :-P $\endgroup$ – chi Jun 15 '18 at 13:53

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.