CS计算机代考程序代写 /Users/billy/gits/moc-2021/problem-sets/solps10.dvi

/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