1
$\begingroup$

Here is a context free grammar that I have been given for practice: Grammar $G = (V,\Sigma,R,S)$ where $V$ is $\{S,A,B,a,b,c\}$ and $\Sigma$ is $\{a,b,c\}$. $R$ has the following rules:

$$\begin{align}S &\to A\\ A &\to BB\\ S &\to bS\\ S &\to cS\\ A &\to a\end{align}$$

I am fairly sure that it is not ambiguous, since for a grammar to be ambiguous there will be two ways to reach a result. In the grammar above, each $b$ comes from $S \to bS$, each $c$ comes from $S \to cS$, and each $a$ comes from $S \to A \to a$. It seems the $A \to BB$ is never used and $c=(b\cup c)^*a$. So there is only one derivative of each string in $L$.

My question is, is my thinking correct and would this suffice to prove that the grammar is not ambiguous?

Edit: We went over the problem in class a while back and the explanation above was accurate.

| cite | improve this question | |
$\endgroup$
  • 2
    $\begingroup$ You already asked this question. I said the grammar was ill-defined because symbol B is used but has no definition. You deleted that question and re-asked a couple minutes later, but did not fix that error. Why? $\endgroup$ – orlp Mar 29 '17 at 6:42
  • $\begingroup$ I deleted this post earlier per the request of the other comment, but was then told that they recommended deleting the other duplicate rather than this one, hence the repost. As for symbol B, the question does not provide any other information than what is above. Since symbol B is not defined, could this be a reason as to why the grammar is unambiguous or would it just make it unsolvable? If it is the latter case, the question itself is flawed. $\endgroup$ – TweezerCube Mar 29 '17 at 6:47
  • 1
    $\begingroup$ Assuming you didn't miss a definition of B somewhere I'd argue that the question itself is indeed flawed. $\endgroup$ – orlp Mar 29 '17 at 6:50
  • 3
    $\begingroup$ @orlp Having a non-terminal symbol that can't generate anything is not a problem, just like having states that aren't co-accessible in an automaton isn't a problem. They are just superfluous. $\endgroup$ – xavierm02 Mar 29 '17 at 9:16
  • 1
    $\begingroup$ Your thinking is correct, and you can use your ideas to formally prove that the grammar is unambiguous. $\endgroup$ – Yuval Filmus Mar 29 '17 at 16:42

Your Answer

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

Browse other questions tagged or ask your own question.