Quiz 2: NFAs and Regular Expressions
[ Solution ]
[ Given In Class Quiz ]

Set Problems Posted
Solution posted
23 Jan 30 Jan
  1. Dragon Book
    Textbook exercise #3.7.3 on page 166, using just algorithm 3.20 (which is given on page 159). Remember, their ε is my λ.
    Crafting a Compiler
    Textbook exercise #17 on page 89, using the structurally inductive technique shown in class
  2. Dragon Book
    Textbook exercise #3.7.1 on page 166
    Crafting a Compiler
    Textbook exercise #4 on page 87
  3. Consider a strange programming language in which identifiers are constructed using symbols from the alphabet Σ = { a, b, c, d, e } Stranger still, the language requires that all identifiers end in a different letter than they begin. Show the (nondeterministic) finite-state automaton that recognizes identifiers in this language.
  4. Consider a language L. Let Rev(L) be the language containing the reverse of each string in L. For example, L contains the string cat if and only if Rev(L) contains the string tac. Show that if L is regular, then Rev(L) is necessarily regular.

    Hint: given a regular expression for R, show how to generate a regular expression for Rev(R), using constructions based on the operators of a regular expression.

  5. Consider the finite-state machine:
  6. Given the FSA shown below, construct the corresponding FSA that doesn't use lambda.
  7. Show an FSA that can recognize comments in the style
        //   stuff up to the newline 
    assuming the comment characters don't show up in the comment text.