SCXT 350
Exercise set #3
Due: Wednesday, Nov. 29 (in class)
Note: This exercise may be done in groups of no
more than two or three. If you do that, each member of the group
should turn in a separate copy with the names of the other members of
the group clearly written at the top.
Consider the following grammar
- A -> aB
- B -> bC
- C -> cD
- D -> bC | d
- Write parse tree derivations for the two strings 'abcd' and
'abcbcd'
- Write derivations for both strings
- Convert the grammar to a finite state automata, and check that
the two strings (above) are correctly recognized.
- Characterize the machine. What does it
recognize/generate?
- Write a "state table" for the machine.
Consider the grammar for expressions:
- E -> E + T | E -
T | T
- T -> T * F | T /
F | F
- F -> x | y | z | ( E )
- Write a parse tree derivation for (x + y) / (x - y)
- Write a derivation for that expression
Please work the two problems at the end of chapter 6 in the textbook
(please note - there may be a mistake in one of them, which we will
discuss in class on Wednesday).
Any questions? Please ask!
-Bob