Reference no: EM131830112

Assignment

Problem 1. Consider the following regular expressions (omitting the dot operator)

R_θ = a | b | c
R₁ = a | b | c | d
R₂ = (a | b) (a* | b*)
R₃ = (a* | b*)R₁ (ab) (ab)*
R₄ = ab R₃* (a | b)*
R₅ = R₃* aaa R₂*

Let getToken() be a function that returns the next token in the input. If we call it repeatedly it will return one token after another. When all the input is consumed, getToken() returns EOF (end of file). Assume that longest prefix-matching rule is used by getToken() and ties are broken in favor of the regular expression listed first.

1. Give an example of input for which getToken() returns R_θ
2. Give an example of input for which getToken() returns R₁
3. Give an example of input for which getToken() returns R₂
4. Give an example of input for which getToken() returns R₃
5. Give an example of input for which getToken() returns R₄
6. Give an example of input for which getToken() returns R₅
7. If getToken() is called repeatedly on the following input, what is the sequence of tokens and lexemes returned? In your work, show step by step the Matched, Potential (Viable), and Maximal tokens.

aaadbabaadaaadabbbaab

Problem 2. Let R₁ and R₂ be two regular expressions,

1. Is it alwaysthe case that L(((R₁)*)|((R₂)*)) = L(((R₁)|(R₂))*)?
2. Is it alwaysthe case that L(((R₁)*).((R₂)*)) = L(((R₁).(R₂))*)?
3. Is it alwaysthe case that L(((R₁)*|(R₂)*)*) = L(((R₁)|(R₂))*)?
4. Is it always the case that L((R₁*)*) = L((R₁)*)?

In each case explain why the statement is true or provide a counter example.

Problem 3. Consider the grammar

S → X Y
X → aX | b
Y → bbY | E

Draw a parse tree for input string aabbb

Problem 4. Consider the grammar

S → X Y
X → YaX | Y b
Y → aXYY | X X Y | E

1. What are the non-terminals?
2. What is the start symbol?
3. What are the terminals?
4. Show that this grammar is ambiguous by constructing two different parse trees for the string abab