CS314 Fall 2018 Assignment 2 Solutions
Problem 1
For both (a) and (b), qi is the state representing ”i mod 4”. In both cases, q0 is the start state.
(a)
q0 q1 q2 q3
1
0
1
0
0
0 1
1
(b)
q0 q1 q2 q3
1
0
1
0
0
0 1
1
Problem 2
(a)
::= a | a
::= ab | ε
(b)
::= abbb | ε
(c)
::= aa | bb | ε
1
(d)
The language {anbncndm | n ≥ 0,m ≥ 0} is not context-free. Trying different rules, one can see why
it would fail to generate this language. You may also use the pumping lemma.
(e)
Problem 3
(a)
Left-most derivation:
1.
2. →L
3. →L
4. →L ∨
5. →L a ∨
6. →L a ∨
7. →L a ∨
8. →L a ∨ false ∧
9. →L a ∨ false ∧
10. →L a ∨ false ∧ →
11. →L a ∨ false ∧ b →
12. →L a ∨ false ∧ b →
13. →L a ∨ false ∧ b → false
Right-most derivation:
1.
2. →R
3. →R
4. →R
5. →R
6. →R
7. →R
8. →R
9. →R
10. →R
11. →R
12. →R ∨ false ∧ b → false
13. →R a ∨ false ∧ b → false
(b)
Left-most parse tree:
false
→
b
∧
false
∨
a
2
Right-most parse tree:
false
→
b
∧
false
∨
a
(c)
AST for left-most derivation:
∨
∧
→
falseb
false
a
AST for right-most derivation:
→
false∧
b∨
falsea
(d)
For example, suppose we have the string: a ∨ b ∧ c. Then we have the following left-most derivations.
Left-most derivation #1:
1.
2. →L
3. →L
4. →L ∨
5. →L a ∨
6. →L a ∨
7. →L a ∨ ∧
8. →L a ∨ b ∧
9. →L a ∨ b ∧
10. →L a ∨ b ∧ c
Left-most derivation: #2
1.
2. →L
3. →L
4. →L
5. →L ∨
6. →L a ∨
7. →L a ∨ ∧
8. →L a ∨ b ∧
9. →L a ∨ b ∧
10. →L a ∨ b ∧ c
Since this string has two possible left-most derivations the grammar is ambiguous.
3
(e)
The new grammar looks like the following, by adding new non-terminals
::= a|b|c|…|z
(f)
Parse tree for “a ∨ true ∧ b → false ∨ true”:
true
∨
false
→
b
∧
true
∨
a
AST for “a ∨ true ∧ b → false ∨ true”:
→
∨
truefalse
∨
∧
btrue
a
4
Extra Credit – Problem 4
Yes, we can. For example, we can change the grammar to be:
by adding the non-terminals
if x = 0 then if y = 0 then z := 1 else z := 2 will have the following parse tree with this new
grammar:
2
:=
z
else
1
:=
z
then
0=
y
if
then
0=
x
if
Notice that at depth = 3 (with the root of the tree having depth = 1), we cannot replace
by
requires that the middle non-terminal
then, and else.
Also, notice that no new terminals were added.
5