程序代写代做代考 CS314 Fall 2018 Assignment 2 Solutions

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

0 1

(b)

q0 q1 q2 q3

0 1

Problem 2

(a)

~~::=~~

::= a | a
::= ab | ε
::= c | c

(b)

~~::= a~~bbb | ε~~~~

(c)

~~::= a~~a | b~~b | ε~~~~~~

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)
~~::=~~

::= a | b | ε

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 → false
6. →R ∧ → false
7. →R ∧ → false 8. →R ∧ b → false 9. →R ∨ ∧ b → false

10. →R ∨ ∧ b → false
11. →R ∨ false ∧ b → false
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 , , and
:

::=

::= → |
::= ∨ |

::= ∧ |
::= | ::= true | false ::= 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:

::=

::= |
::= ifthenelse |
::= ifthen | ifthenelse
::= :=

::= = 0

::= 0|1|2|3|4|5|6|7|8|9
::= a|b|c| . . . |z

by adding the non-terminals and , replacing . The statement
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 , since the rule

::= if then else

requires that the middle non-terminal must be replaced with a string that contains if,
then, and else.

Also, notice that no new terminals were added.

5

Related Posts