This statement is the intuitive part that requires a (hard) formal proof; could there be some other way for P to compare equal blocks of Os?

there are pairs of strings in this language one of which is a prefix of the other, so this language does not have the prefix property. In fact, of any two strings, one is a prefix of the other, although that condition is stronger than we need to establish that the prefix property does not hold. □

Note that the language {0}* is a regular language. Thus, it is not even true that every regular language is N{P) for some DPD.4. P. We leave as an exercise the following relationship:

Theorem 6.19: A language L is N(P) for some DPDA P if and only if L has the prefix property and L is i(P) for some DPDA P. □

6.4.3 DPDAs and Context-Free Languages

We have already seen that a DPDA can accept languages like i ,c,i;r that are not regular. To see this language is not regular, suppose it were, and use the pumping lemma. If n is the constant of the pumping lemma, then consider the string w = 0 cO, which is in Lcujt- However, when we pump this string, it is the first group of Os whose length must change, so we get in Lwcwr strings that have the center marker not in the center. Since these strings are not in Ewcwr, we have a contradiction and conclude that L,i-uir is not regular.

On the other hand, there are CFLs like Lwr that cannot be L{P) for any DPDA P. A formal proof is complex, but the intuition is transparent. If P is a DPDA accepting Ь,,., then given a sequence of Os, it must store them on the stack, or do something equivalent to count an aibitrary number of Os. For instance, it cotdd store one X for every two Os it sees, and use the state to remember whether the mnnber was even or odd.

Suppose P has seen n Os and then sees 110 . It must verify that there were n Os after the 11, and to do so it must pop its stack, Now, P has seen 0 110 . If it sees an identical string next, it must accept, because the complete input is of the form ww, with w = 0 110 . However, if it sees 0 110 for some тфп, P must not accept. Since its stack is empty, it caimot remember what arbitrary integer n was, and must fail to recognize Lwr correctly. Our conclusion is that:

The languages accepted by DPD.4s by final state properly include the regular languages, but are properly included in the CFLs.

6.4.4 DPDAs and Ambiguous Grammars

We can refine the power of the DPDAs by noting that the languages they accept all have unambiguous grammars. Unfortunately, the DPDA languages are not

The proof of Theorem 6.19 appears in Exercise 6.4,3, but we can easily see how to construct P from P. Add a new state q that P enters whenever P is in an accepting state and the next input is $. In state q, P pops all symbols off its stack. Also, P needs its own bottom-of-stact; marker to avoid accidentally emptying its stack as it simulates P.

exactly equal to the subset of the CFLs that are not inherently ambiguous. For instance, Lj. has an unambiguous grammar

5 050 I 151 I e

even though it is not a DPDA language. The following theorems refine the bullet point above.

Theorem 6.20: If L 7V(F) for some DPDA F, then L has an unambiguous context-free grammar,

PROOF: We claim that the construction of Theorem 6.14 yields an unambiguous CFG G when the PDA to which it is applied is deterministic. First recall from Theorem 5.29 that it is sufficient to show that the grammar has unique leftmost derivations In order to prove that G is unambiguous.

Suppose P accepts string w by empty stack. Then it does so by a unique sequence of moves, because it is deterministic, and cannot move once its stack is empty. Knowing this sequence of moves, we can determine the one choice of production in a leftmost derivation whereby G derives w. There can never be a choice of which rule of P motivated the production to use. However, a rule of F, say 6{q, a, X) - {{r, Y1Y2 Yk)} might cause many productions of G, with different states in the positions that reflect the states of F after popping each of Yi, У2,.,., Yk-1 Because F is deterministic, only one of these sequences of choices will be consistent with what F actually does, and therefore, only one of these productions will actually lead to derivation of w. О

However, we can prove more: even those languages that DPDAs accept by final state have unambiguous grammars. Since we only know how to construct grammars directly from PDAs that accept by empty stack, we need to change the language involved to have the prefix property, and then modify the resulting grammar to generate the original language. We do so by use of an endraarker sjmibol.

Theorem 6.21: If L = L(F) for some DPDA F, then L has an unambiguous CFG.

PROOF: let $ be an endmarker symbol that does not appear in the strings of L, and let L - L$. That is, the strings of L are the strings of L, each followed by the symbol $. Then L surely has the prefix property, and by Theorem 6,19, L iV(F) for some DPDA F. By Theorem 6,20, there is an unambiguous grammar G generating the language iV(F), which is L.

Now-, construct from G a grammar G such that LCG) = L. To do so, we have only to get rid of the endmarker $ from strings. Thus, treat $ as a variable

of G, and introduce production $ e; otherwise, the productions of G and G are the same. Since L{G) - L, it follows that L{G) L.

We claim that G is unambiguous. In proof, the leftmost derivations in G are exactly the same as the leftmost derivations in G, except that the derivations in G have a final step in which $ is replaced by e. Thus, if a terminal w string had two leftmost derivations in G, then w$ would have two leftmost derivations in G. Since we know G is unambiguous, so is G. □

6.4.5 Exercises for Section 6.4

Exercise 6.4.1: For each of the following PDAs, tell whether or not it is deterministic. Either show that it meets the definition of a DPDA or find a rule or rules that violate it.

a) The PDA of Example 6.2.

* b) The PDA of Exercise 6.1.1. c) The PDA of Exercise 6.3.3.

Exercise 6.4.2: Give deterministic pushdown automata to accept the following languages:

a) {0 1 I n<m}.

b) {0 1 \n>m}.

c) {0 1 0 I n and m are arbitrary}.

Exercise 6.4.3: We can prove Theorem 6.19 in three parts:

* a) Show that if L = N{P) for some DPDA F, then Lhas the prefix property.

! b) Show that if L = N{P] for some DPDA P, then there exists a DPDA P such thatL = L(P)-

*! c) Show that if L has the prefix property and is L{P) for some DPDA P, then there exists a DPDA P such that L = N{P).

и Exercise 6.4.4: Show that the language

L = {O ! I n > 1} и {0 1 I и > 1}

is a context-free language that is not accepted by any DPDA. Hint: Show that there must be two strings of the form 0 1 for different values of n, say щ and П2 that cause a hypothetical DPDA for L to enter the same ID after reading both strings. Intuitively, the DPDA must erase from its stack almost everything it placed there on reading the Os, in order to check that it has seen the same number of Is. Thus, the DPDA cannot tell whether or not to accept next after seeing Ui Is or after seeing Is.