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,

- Provide a simple (as simple as you can make it by inspection) nondeterministic FSA that accepts the language.
- Make that machine deterministic.

- The language of all binary strings that end with "11".
Examples include 11, 011, and 10111.
- 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