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.