HOMEWORK 1
All submissions must be PDF and should be typed. Exception can only be made for drawing parse
trees, which can be handwritten and scanned in the submitted document.
Note. Some of these problems are taken from the Dragon book.
Problem 1. Consider the following regular expressions (we omit the dot operator)
R0 = 1|2|3|4|5|6|7|8|9
R1 = 0|1|2|3|4|5|6|7|8|9
R2 = (0|1)* R0 (0|1)
R3 = 00 R0*(0|1)*
R4 = R3* R2* 000
Assume that the longest prefix-matching rule is used. Assume that ties are broken in favor of the
regular expression listed first in the list.
1. Give an example of input for which getToken() returns R0
2. Give an example of input for which getToken() returns R1
3. Give an example of input for which getToken() returns R2
4. Give an example of input for which getToken() returns R3
5. Give an example of input for which getToken() returns R4
6. If getToken() is called repeatedly on the following input, what is the sequence of tokens
returned?
99001101678100010101030123457000010
Explain your answers.
Problem 2. Consider the grammar
S → AB
A → BaA | bB
B → aSB | AS | ε
1. Show that this grammar is ambiguous by constructing two different leftmost derivations for the
sentence abab
2. Show that this grammar is ambiguous by constructing two different parse tresses for the string
abab
Problem 3. Compute FIRST sets for the following grammar.
S → aAB | CD
A → CD | SE | ε
B → aSB |AS
C → cC | ε
D → CDd | ε
E → eFg
F → Fg | ε
Show your work. An answer by itself does not count.
