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.

1 CFSM Practice

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

Seven
eveneven WIN even LOSS
evenLOSS 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. (OPTIONAL enrichment) Give an SLR(1) grammar for this language, or prove that none exists.