# Tag Info

2

Sems to be a decent approach. The trick you need is to leave the last B marked, say you generate bbX rather than bbb. Now the final X can absorb the C's using the production CX -> aX. In the end you are left with the final X which can change into b again. Of course the final production X -> b might be applied too soon, when there are still C's ...

0

Your grammar $$\begin{eqnarray}S &\to& aSb &|& A \\ A &\to& aaAb &|& \epsilon\end{eqnarray}$$ is indeed unambiguous. The production $S \to A$ must occur precisely once in any derivation, and the productions which precede it cannot be replaced with any productions which succeed it or vice versa.

2

The language $L$ clearly exists — you just defined it! It’s not hard to check that your language is co-r.e., that is, you can enumerate ambiguous grammars. Since it’s not recursive, it cannot be r.e.

1

Precedence and associativity declarations are common in parser generators, but they are not part of the theory of context-free grammars. And nor are they part of the working of the LL(k) parsing algorithms (or, for that matter, the LR(k) algorithms). So there is no real way to answer that question in terms of the theory of formal languages. On a practical ...

1

Your first language isn't regular. Here is a simple way of showing this. Consider all words in your language of the form $a^*c^*$; if your language were regular, then so would be that language. However, the new language is generated by the grammar $L \to \epsilon \mid aLcc$ (this requires an argument), and so is $\{a^n (cc)^n : n \geq 0\}$, which is ...

Top 50 recent answers are included