Past exam of the computer science course of the University of Oxford / 2015 / Models of computation / 2 / b

A context-free grammar is an ambiguous grammar if some word in its generated formal language has two distinct parse trees. Equivalently, that word has two distinct leftmost derivations from the start nonterminal symbol. A leftmost derivation always expands the leftmost remaining nonterminal symbol.

Two arbitrary grammar derivations of the same word do not by themselves prove ambiguity: expanding independent nonterminal symbols in a different order can describe the same parse tree. Requiring distinct parse trees, or distinct leftmost derivations, avoids that issue.

The word $abb$ has these two leftmost derivations:In the first grammar derivation, $U\to aT$ supplies an extra $b$; the remaining $S$ goes directly to the empty word. In the second grammar derivation, $U\to a$ is used, and the remaining $S$ uses $S\to ST$ before disappearing. Every step expands the leftmost nonterminal symbol, so these are genuinely different leftmost derivations, with different parse trees already distinguished by the production rule at the $U$ node.

Use the standard conversion of a context-free grammar to a pushdown automaton, implementing a leftmost derivation on a stack. Take control states $q_s,q,q_f$, input alphabet $\{a,b\}$, stack alphabet $\{S,T,U,a,b,\perp \}$, initial control state $q_s$, initial stack symbol $\perp$, and sole final control state $q_f$. The symbol $\perp$ is a fresh stack bottom marker. As in part (a), the top of the stack is written on the left.

Initialize withIn control state $q$, replace a top nonterminal symbol by one of its production rule right-hand sides:The replacements are written in the order in which they are to be processed. For example, replacing $S$ by $UST$ leaves $U$ on top; an implementation using individual push operations pushes $T$, then $S$, then $U$.

Match and pop top terminal symbols byFinally includeAll unlisted transitions have no choices; $q_f$ has no outgoing transitions. This is acceptance by final state, leaving the bottom marker on the stack. Taking the last transition too early cannot cause false acceptance, because an unread input suffix remains and $q_f$ cannot consume it.

For correctness, after initialization the stack contains the unprocessed part of a sentential form. Expanding a top nonterminal symbol simulates one step of a leftmost derivation, and popping a matching terminal symbol transfers it to the already-read input prefix. Thus if the input prefix consumed so far is $u$ and the stack above $\perp$ is $\alpha$, then $S{\Rightarrow }_G^{\ast }u\alpha$. Acceptance gives $S{\Rightarrow }_G^{\ast }w$ for the entire input $w$.

Conversely, any leftmost derivation of $w$ specifies choices of these transitions: expand the next nonterminal symbol, and read each resulting leading terminal symbol when it reaches the top. After all symbols of $w$ are consumed, only $\perp$ remains, enabling the move to $q_f$. The nondeterministic pushdown automaton therefore recognizes exactly $L(G)$. The empty word is accepted by choosing $S\to \epsilon$ after initialization.

Every generated word satisfieswhere ${\#}_a,{\#}_b$ count occurrences of the indicated terminal symbols. To see this, follow the unique chain of $S$ occurrences in a parse tree. Each use of $S\to UST$ introduces one $a$ from $U$, at least one $b$ from its rightmost $T$, and possibly one further $b$ from $U\to aT$. Each use of $S\to ST$ adds one $b$ and no $a$. The terminating $S\to \epsilon$ contributes neither. Hence no generated word has more $a$ symbols than $b$ symbols.

Also, for every $n\ge 0$, the word $a^n{b}^n$ is generated: apply $S\to UST$ exactly $n$ times, choose $U\to a$ each time, then use $S\to \epsilon$ and all remaining $T\to b$.

Suppose $L(G)$ were a regular language, and let $p\ge 1$ be a pumping length from the pumping lemma for regular languages. Apply it to $w=a^p{b}^p$. Every allowed decomposition $w=xyz$ with $|xy|\le p$ and $|y|>0$ has $y=a^r$ for some $r\ge 1$. Pumping twice giveswhich violates the proved counting inequality and hence is not generated. This contradicts the pumping lemma for regular languages. Therefore $L(G)$ is not a regular language. Ambiguity was not used: the obstruction is the unbounded constraint on symbol counts.