1
$\begingroup$

For a given context-free grammar (CFG) you can always construct a pushdown automaton PDA (and vice-versa). This pushdown automaton is possibly non-deterministic, since for a non-terminal $X$ in the CFG, there might be multiple rules of the form $X \rightarrow \gamma$.

The book I am using says that this looks like it could lead to ambiguity in the language, but that this isn't the case. My first question is why this is. To me at least, it seems like this should imply ambiguity.

Following this the book states the question "If there is a deterministic PDA that determines a language $L$, is $L$ non-ambiguous?". I can't see how you could argue this to be true (or false) or how to construct a proof for it. With ambiguity being the existence of multiple left/rightmost derivations for a given input string.

Improve this question
$\endgroup$
4
  • $\begingroup$ I suggest you start by checking the definition of ambiguity for a language and ambiguity for a grammar. Do you know them? Try writing them down and applying them to this situation and see what you get. Hint: I suspect you don't mean to ask about whether the language is ambiguous. See cs.stackexchange.com/q/103077/755. $\endgroup$
    – D.W. ♦
    Commented Jan 23, 2022 at 21:57
  • $\begingroup$ No I don't know the true definition. There is no strict definition in my textbooks and Google only seemed to return this: "ambiguity is the existence of multiple left/rightmost derivations for a given input string". $\endgroup$
    – Matthias K.
    Commented Jan 23, 2022 at 22:03
  • $\begingroup$ I can make a few suggestions. 1) You can give a full quote from the textbook, with context. 2) You can read the link (and en.wikipedia.org/wiki/…) to understand various possible notions of ambiguity, and consider how they might apply to your statement. In particular, as far as I know, the only notion for languages is "inherently ambiguous" (I've never heard of any notion of "ambiguous", except perhaps when someone uses the term loosely to actually mean the same as inherently ambiguous). $\endgroup$
    – D.W. ♦
    Commented Jan 24, 2022 at 0:45
  • $\begingroup$ The wikipedia link certainly helps clarifying. Would it in your opinion, to prove something like this, be a good idea to start from a deterministic PDA and use the fact that it can be transformed into a CFG? Still where I'd be stuck is on how to prove such a CFG is unambiguous (it would now be the grammar for which to prove the (un)ambiguity) so I think there's no notion of "inherently ambiguous"? $\endgroup$
    – Matthias K.
    Commented Jan 24, 2022 at 9:49

1 Answer 1

Reset to default
3
$\begingroup$

Basically, the statement is true: when we have a deterministic PDA for a language $L$, we can construct a non-ambiguous grammar for $L$.

The notions of determinism and non-ambiguity are related, but we should be cautious. Determinism for PDA is a kind of 'local' property: In each configuration (state, input symbol, top of stack) the PDA has only a single possible continuation. Non-ambiguity is more 'global': for each word in the language the grammar has only a single derivation tree (or equivalently, a single leftmost derivation).

The two notions are not equivalent: the language of palindromes over a two-letter alphabet does not have a deterministic PDA (it cannot determine when to switch from pushing to popping) but it has a very simple non-ambiguous CFG.

In fact the 'standard' construction from PDA to CFG translates a deterministic PDA into a non-ambiguous grammar. By the construction each leftmost derivation will correspond to a PDA computation. As the deterministic PDA has only a single computation, there will be only a single leftmost derivation.

The above is the basic observation, but unfortunately it is not true if we do not take some technical precautions. First, the standard construction works if we start from a PDA that accepts by empty stack, and not the usual accaptance by final state. This is a restriction, languages accepted by empty stack are necessarily prefix-free (if a string is in the language, none of its prefixes are). Second, the observation that a deterministic PDA has only a single accepting computation, is not completely true: after accepting the automaton may keep computing with $\epsilon$-moves, and accept the same input again.

Both these problems can be avoided by considering the language $L{\\\$}$ instead of $L$. Here ${\\\$}$ is a special end-marker. Using the end-marker the PDA can be instructed to clear its stack, and we have empty stack acceptance. Then we obtain a non-ambiguous CFG from the deterministic PDA. Finally we may drop $\\\$$ from the grammar, without really changing the derivations, so without causing ambiguity.

Improve this answer
$\endgroup$
2
  • $\begingroup$ This is certainly very helpful! So if I'm not mistaken, you would take a language with alphabet $\Sigma \cup \{\$\}$ and use the $\$$ sign to let the PDA be able to distinguish between pushing/popping on/off the stack? $\endgroup$
    – Matthias K.
    Commented Jan 24, 2022 at 9:55
  • $\begingroup$ The special symbol is used to signal the end of the string, so we may (deterministically) switch from final state acceptance to empty stack acceptance. Indeed at the end of the string the automaton will pop all symbols from the stack, provided the state is final. This is different from the language of palindromes where the PDA must guess (nondeterministically!) the middle, unless the middle is explicitly indicated: $\{ wcw^R \mid w\in\{a,b\}^* \}$. $\endgroup$
    – Hendrik Jan
    Commented Jan 24, 2022 at 21:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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