CSE 340 HOMEWORK 1

Problem 1 out of 2. Consider the following regular expressions (I am omitting the dot operator)!R0 = b+c+d+e+fR1 = a+b+c+d+e+fR2 = (a*+b*)(a+b)R3 = (a+b)* R1 (a+b)R4 = aa R0*(a+b)*R5 = R3* R2* aaa !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, geToken() returns EOF (end of file). Assume that longest prefix-matching rule is used by getToken(). 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 R02. Give an example of input for which getToken() returns R13. Give an example of input for which getToken() returns R24. Give an example of input for which getToken() returns R35. Give an example of input for which getToken() returns R46. Give an example of input for which getToken() returns R57. If getToken() is called repeatedly on the following input, what is the sequence oftokens returned? In your work, show step by step the MATCHED, the POTENTIALMATCHED, and the MAXIMAL MATCHED tokens. ffaabbabcdebaaabababcdefaaba 
For questions 1-6 you should explain your answers
Problem 2 out of 2. Consider the grammar


S AB

A BaA I Bb

B aSB I AS I E

What are the non-terminals?

What is the start symbol?

What are the terminals?

Show that this grammar is ambiguous by constructing two different parse tress for the

string abab
Powered by