Quiz 2: NFAs and Regular Expressions

Quiz Posted
(Thursdays)
Given in class
(Thursdays)
24 Jan 31 Jan
  1. Given the FSA shown below, construct the corresponding deterministic FSA.

  2. Derive the regular expression for the language accepted by that FSA.
  3. (Extra credit) Given a pumping-lemma style argument that the set of palindromes over the alphabet Σ={a,b} is not a regular language.
  4. Consider the following grammar:
       Start  ->  E $
       E      ->  T + E
              |   T
       T      ->  T * F
              |   F
       F      ->  ( E )
              |   a
    
  5. For each grammar shown below, answer the following. Is the grammar ambiguous? If so, provide two distinct derivations for the same input string; if not, describe what makes this grammar unambiguous.