1. Dragon book: parts a, b, and c can each be denoted by an FSA of one accepting state with transitions to itself on a or b.

    CaC book: The NFA could be:

    The determinsitic construction is then given by:
    State a b c
    [A] [BD]
    [BD] [BE] [C]
    [BE] [B] [CE]
    [B] [B] [C]
    [CE] [E]
    [E] [E]
    The accepting states are C, CE, and E.
  2. Ask in class
  3. Ask in class
  4. Language is infix arithmetic expressions involving operators + and *, with "a" as the only identifier, terminated by $.
    Right linear grammar:
      A ->  a B
      B ->  + A
         |  * A
         |  $ C
      C -> lambda
  5. Given by the construction:
    State s lambda-close(s) eat a lambda-close after a eat b lambda-close after b eat c lambda-close after c
    A A B A,B
    B A,B B A,B B,C A,B,C
    C A,B,C B A,B B,C A,B,C C A,B,C
    And C remains the only accept state (no other state can lamba-coast to C.

    In picture form:

  6. Ask in class