/Users/billy/gits/moc-2021/problem-sets/solps10.dvi
The University of Melbourne
School of Computing and Information Systems
COMP30026 Models of Computation
Selected Problem Set Solutions, Week 10
P10.1 Here is a PDA for {w | the length of w is odd and its middle symbol is 0}
ǫ, ǫ → $ 0, ǫ → ǫ ǫ, $ → ǫ
0, ǫ → x
1, ǫ → x
0, x → ǫ
1, x → ǫ
P10.3 For the case v 6= ǫ we define
δ((qp, qd), v, x) =
{
((rp, rd), y)
∣
∣ (rp, y) ∈ δP (qp, v, x) ∧ rd = δD(qd, v)
}
But we must also allow transitions that don’t consume input, so:
δ((qp, qd), ǫ, x) =
{
((rp, qd), y)
∣
∣ (rp, y) ∈ δP (qp, ǫ, x)
}
P10.5 We are looking at the context-free grammar G:
S → A B A
A → a A | ǫ
B → b B | ǫ
(a) The grammar is ambiguous. For example, a has two different leftmost derivations:
S ⇒ A B A ⇒ B A ⇒ A ⇒ a A ⇒ a
S ⇒ A B A ⇒ a A B A ⇒ a B A ⇒ a A ⇒ a
(b) L(G) = a∗b∗a∗.
(c) To find an unambiguous equivalent context-free grammar it helps to build a DFA for
a
∗
b
∗
a
∗. (If this is too hard, we can always construct an NFA, which is easy, and then
translate the NFA to a DFA using the subset construction method, which is also easy.)
Below is the DFA we end up with. The states are named S, T , and U to suggest
how they can be made to correspond to variables in a context-free grammar. The DFA
translates easily to the grammar on the right. The resulting grammar is a so-called
regular grammar, and it is easy to see that it is unambiguous—there is never a choice of
rule to use.
S T U ∅
b a b
a b a a,b
S → ǫ | a S | b T
T → ǫ | b T | a U
U → ǫ | a U
P10.6 Here is a context-free grammar that will do the job (S is the start symbol):
S → ǫ | a A
A → a A | b B
B → ǫ | a A | b B