CPSC 433: Quiz 3
January 31, 2006
"On my honor, as an Aggie, I have neither given nor received
unauthorized aid on this academic work.
In particular, I certify
that I have not received or given any assistance that is
contrary to the letter or the spirit of the collaboration
guidelines for this assignment."
- (1 pt) True or False: Every deterministic finite automaton
can be converted into an equivalent nondeterministic finite automaton.
- (1 pt) True or False: Every nondeterministic finite automaton
can be converted into an equivalent deterministic finite automaton.
- (1 pt) True or False: There exists a nondeterministic
finite automaton with epsilon transitions that cannot be converted
into a deterministic finite automaton.
- (2 pts) Give the recursive definition for regular expressions.