Quiz 2: NFAs and Regular Expressions

Quiz Posted
Given in class
17 Jan 24 Jan
  1. Textbook exercise #17 on page 89, using the structurally inductive technique shown in class.
  2. 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. Textbook problem #21 on page 90. 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.