## Ars Digita University

Theory of Computation

Recitation 1, 05/03/01

## Topics

- Languages
- All computational problems can be reframed as questions
of membership in a language (set).
- Drawing Deterministic Finite Automata (DFAs).
- Drawing Nondeterministic Finite Automata (NFAs).
- Converting NFAs to DFAs
- Regular Languages, Closure properties of Regular languages.

## Problems to work on

- What is a language?
- Draw a DFA that accepts the strings ending in 01.
- Draw a DFA that accepts the strings that have an even number of zeros.
- Draw a DFA that accepts the strings that have an even number of zeros
or end in 01.
- Draw a DFA that accepts the strings that have an even number of zeros
and end in 01.
- Draw a DFA that accepts the strings that have an even number of zeros
but don't end in 01.
- Draw an NFA that accepts the strings that end in 01. Try to make it
as simple as possible.
- Draw an NFA that accepts the strings that have an even number of zeros
or end in 01 using six states.
- Draw an NFA that accepts any string that is a concatenation of a string
that has an even number of zeros with a string that ends in 01.
- Draw an NFA that accepts the strings that have an even number of zeros
and end in 01.
- Draw an NFA that accepts the language 0, using only two states.
- Convert the previous NFA into a DFA using the method described in class.
- Draw an NFA with two states that corresponds to the language 0?2*.
- Convert the previous NFA to a DFA.
- What is a regular language?
- Draw the DFA that corresponds to the language 10*10*.
- What is the Prefix of the language corresponding to the language 10*10*.
- Draw the DFA for the prefix of the language corresponding to the
regular expression 10*10*.
- What is the MIN of the language 10*10*?
- Draw the DFA corresponding to the MIN of the language 10*10*.

Dimitri Kountourogiannis, dimitrik@alu\
m.mit.edu