CFL production

Question

Are grammars with $S \to SS$ productions always ambiguous?

Also, how can the production be represented in form of a formula? For example, $S \to aSb \mid \varepsilon$ can be written as $S = a^n b^n$

What would be the formula for $S \to aSb \mid SS \mid \varepsilon$?

Answer 1

I think this grammar is unambiguous (Note: proving unambiguity for an arbitrary CFG is undecidable!):

$$\begin{align}
S &\to SS \mid aA \mid bB\\[1em]
A &\to aA \mid \alpha\\[1em]
B &\to bB \mid \beta
\end{align}$$

About converting a grammar to a formula, the grammar is a formula! If you want a formula of the type $a^x b^y c^z$, it is neither always obvious nor always possible!

For example, the $S \to aSb \mid SS \mid \varepsilon$ can't be put into a nice looking formula. It describes balanced parenthesis, where $a$ is the opening paren, and $b$ is the closing paren.

Comments

Thank you for the explanation :) ....i found a representation for above grammar as (a^n.b^n)^* and is it correct..??

---

You mean for this? $S \to aSb \mid SS \mid \varepsilon$. Nopes.

$(aaa(ab)(ab)bbb)$ can be derived from $S$, right? (Ignoring the parens).

$(a^n b^n)^*$ doesn't contain it!