Problem Consider the following regular expressions R1-124 |8 R2(a | b) (a* | b*)

Question

Problem Consider the following regular expressions R1-124 |8 R2(a | b) (a* | b*) (a | b) In the expressions, the dot operator is omitted and some parentheses are omitted, in which case the Kleene star operator () has the highest precedence, followed by the dot operator (.), followed by the or operator (I) 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 calling getToken () twice returns Ro first then EOF 2. Give an example of input for which calling getToken ) twice returns Ri first then EOF 3. Give an example of input for which calling getToken) twice returns R2 first then EOF

Explanation / Answer

Regular expressions :

R0 = 1 | 2 | 3

R1 = 1 | 2 | 4 | 8

R2 = (a | b) (a* | b* ) (a | b )

R3 = (a* | b* ) R1* (ab)*

R4 = ab R3* (a | b)*

R5 = R3* aaa R2*

Given that getToken() be a function that returns the nextToken() in the input.

When all the input is consumed, getToken() returns EOF

1.

Example of input for which getToken() twice returns R0 first then EOF : 1

Considering longest rule matching rule is used by getToken(), calling getToken() twice will return R0 first as '1' is input of R0. Once input gets consumed calling getToken() again returns EOF.

'1' is also an input of R1 but as R0 appears before R1 getToken() returns R0 and then EOF.

2.

Example of input for which getToken() twice returns R0 first then EOF : 4

Considering longest rule matching rule is used by getToken(), calling getToken() twice will return R1 first as '4' is string that can be generated by R1 and then EOF. Calling getToken() again reaches end of file so getToken() returns EOF.

3.

Example of input for which getToken() twice returns R2 first then EOF : aa

Considering longest rule matching rule is used by getToken(), calling getToken() twice will return R2 first as 'aa' is input of R2 and then EOF. Once input gets consumed calling getToken() again returns EOF.

'aa' is also an input of R3 but as R2 appears before R3 getToken() returns R2 and then EOF.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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