the following grammar generates all regular expressions over the alphabet of let

Question

the following grammar generates all regular expressions over the alphabet of letters (we have used quotes to surround operators, since the vertical bar is an operator as well as a metasymbol):
rexp->rexp “|” rexp
| rexp rexp
| rexp “*”
| “(” rexp “)”
| letter

a give a derivation for the regular expression (ab|b)* using this grammar.
b show this grammer is ambiguous

Explanation / Answer

1. rexp->rexp"|" rexp 2. | rexp rexp 3. | rexp "*" 4. "("rexp")" 5. letter a) Use 4th rule rexp -> (rexp) Use 3rd rule (rexp) -> (rexp)* Use 1st rule (rexp)* -> (rexp|rexp)* Use 2nd rule (rexp|rexp)* -> (rexp rexp|rexp)* Use 5th rule (rexp rexp | rexp)* -> (ab|b)* So the order of rules we used to determine the regular expression is 4 3 1 2 5 B) Ambiguous Grammer : is a grammer in which a string can be produced by more than one ways using the production rules. So 1 method i suggested above. 2nd method is - Use the rules in the order of 3 4 1 2 5 i.e. Use 3rd rule rexp -> rexp* Use 4th rule rexp* -> (rexp)* Use 1st rule (rexp)* -> (rexp|rexp)* Use 2nd rule (rexp|rexp)* -> (rexp rexp|rexp)* Use 5th rule (rexp rexp | rexp)* -> (ab|b)* So we are getting two ways, hence the grammer is ambiguous

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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