COM1350 Automata Theory Exam 2 Spring 1998 Professor Fell
Name:
Problem 1:
(5 points)
Describe the language recognized by the Nondeterministic Finite State Automaton.
Problem 2:
(30 points)
Give a Nondeterministic Finite State Automaton with the specified number of states
recognizing each of the following languages. The alphabet is { 0, 1 }
a)
{ w | w = x01 where x has exactly one 1 and any number of 0s } 4 states
b)
{ 103k | k >= 0 } = { 1, 1000, 1000000, . . . } 4 states
c)
{ w | every odd position of w is a 1 } 2 states
Problem 3.
(15 points)
Let
S = { a, b }. Follow the constructions of chapter 1
to create NFAs that recognize these regular expressions:
ia) a
ib) b
ii) a*
iii) a*b
iv) aa
v) a*b 
aa
Problem 4.
(25 points)
Apply the construction of chapter 1
to convert the following NFA to a DFA.
The Second Problem 4.
(15 points)
Follow the construction of chapter 1 in the order given below
to convert the following automata
M
to a regular expression:
a) Convert M to a GNFA
b) Rip state 
1 --> 2
R1 =
R2 =
R3 =
R4 =
c) Rip state 
1 --> A
R1 =
R2 =
R3 =
R4 =
1 --> 1
R1 =
R2 =
R3 =
R4 =
d) Rip state 
S --> A
R1 =
R2 =
R3 =
R4 =
e) The regular expression is:
Problem 5.
(10 points)
Use the pumping lemma to show that the following language is NOT regular.
L = { w | w = xa|x| } where |x| is the length of x.
Last Updated: May 9, 1997 12:35 pm by
Harriet Fell
College of Computer Science, Northeastern University
360 Huntington Avenue #161CN,
Boston, MA 02115
Internet: fell@ccs.neu.edu
Phone: (617) 373-2198 / Fax: (617) 373-5121
The URL for this document is:
http://www.ccs.neu.edu/home/fell/COM1350/test2.html
