Homework 6

This is the archived website of SI 413 from the Fall 2013 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

- Print version, with cover page (pdf)
**Due Date**: Monday, October 7

The following grammar represents the language of all "even" records, where there are an equal number of wins and losses:

S→even

even→even`WIN`

even`LOSS`

even→`LOSS`

even`WIN`

even

even→ ε

I want you to draw out the CFSM for this grammar. Remember that this process really has 3 steps:

- Write out all the LR items (the things with bullets)
- Generate the Nondeterministic CFSM using the two kinds of transitions
- Generate the actual (deterministic) CFSM by combining states

But I'll only require you to show the result at the last step, that is, the final CFSM. As a hint, this CFSM has exactly 9 states.

Once you have the CFSM, answer the following questions about it:

- Give an example of a conflict in the CFSM. Identify the state and say whether it is a shift-reduce or reduce-reduce conflict.
- Is this grammar SLR(1)? Why or why not?
- (OPTIONAL enrichment) Give an SLR(1) grammar for this language, or prove that none exists.