Homework 6

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

Use a separate sheet of paper for your answers! Everything should be submitted in one packet, all printed out for me to see.

1 CFSM Practice

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:

  1. Write out all the LR items (the things with bullets)
  2. Generate the Nondeterministic CFSM using the two kinds of transitions
  3. 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:

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