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

Question

Problem 1. Consider the following regular expressions (omitting the dot operator) Re = a | b | c R2 = (a | b) (a" I b*) R (a b") Ri (ab) (ab) 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 Re 2. Give an example of input for which getToken() returns R1 3 Give an example of inut for whih getToken() returne Ro 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 Rs 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

Explanation / Answer

Solution:

1. Example of input for which getToken() returns R0 : a

    As R0 is listed first, we will get R0 from getToken()

2. Example of input for which getToken() returns R1 : d

    Since d is not a lexeme in R0, getToken() will return R1 as R1 is before others.

3. Example of input for which getToken() returns R2 : ab

   As longest prefix -matching rule is used by getToken() , input 'ab' will return R2. 'ab' is also a input of R3 but as R2 appears before R3, therefore it will return R2. Moreover, 'ab' cannot return R0 or R1 as getToken() returns longest prefix matching .

4. Example of input for which getToken() returns R3: dab

'd' is a prefix of R1, if input would be only 'd' then getToken() would have returned R1 but as input is "dab" ,getToken() uses longest prefix rule and returns R3 . R3 is the only expression that satisfies input "dab" before R4 and R5

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.