Theory of Computation
Major Examination 1
Sample Examination

Note: This is the first exam that your instructor has given to students in the past.

1.Deterministic Finite Automata

a.Define DFA.

b.Define what it means for a DFA to accept a string.

c.Give a finite state automation that would accept the language
{ s | s contains exactly two 1ís}.The alphabet is {0, 1}

d.Give the sequence of states of part c that would accept '0110'

e.Exactly how would the automata in part c reject the string '0100'?

f.Define "regular language".

g.Prove:Regular languages are closed under the closure
( * ) operation.

2.Nondeterministic Finite Automata

a.Define NFA

b.Define, from the definition of a NFA, an equivalent DFA.

c.Give an outline of the proof that the DFA you defined in part b is equivalent to the NFA.

d.Convert the NFA on the last page to a DFA using the techniques from class.Show your work.

3.Pumping theorem

a.State the pumping theorem for regular languages.

b.Give an outline of the proof of the pumping theorem.

c.Let L = { anbncn | n >= 1 }.Prove L is not a regular language.

4.Regular expressions

a.Define regular expression

b.Convert the NFA on the last page to a GNFA using the technique given in class.Show the result on the last page.Then remove the state C as the first step in finding a regular expression for the language of the NFA.Show your work.