Quiz 2: Languages, Grammars, Finite-State Automata

Quizzes are closed-books and closed-notes. Be sure to write your name below.

  Name: _________________________________________________

For each of the languages described below,
  1. Provide a simple (as simple as you can make it by inspection) nondeterministic FSA that accepts the language.
  2. Make that machine deterministic.
  1. The language of all binary strings that end with "11". Examples include 11, 011, and 10111.
    
    
    
    
    
    
    
    
    
    
    
    
    
    
  2. The language of all binary strings that have at least two 1s in them. Examples include 11, 00100010000, and 110110.
    
    
    
    
    
    
    
    
    
    
    
    
    
    


Last modified 13:07:09 CST 30 January 2008 by Ron K. Cytron