(a)
(b)
(c)
25. Determine the languages recognized by the given DFA.
(a)
(b)
26. Determine a DFA that recognizes each of the following
(a) { |
, , ,
}
1
1 2 3
n
n =
KK
(b) {1, 00}
(c) {0}
27. Show that there is no finite-state automaton that recognizes the set of bit
strings containing an equal number of 0
s and 1
s
.
28. What are the strings in the regular sets specified by the regular
expressions given below.
(a) 10
*
(b) (10)
*
(c) 0 01
∪
(d) 0 0 1
(
)
*
∪
(e) (0 * 1)
* .
29. Construct a NDA that recognizes the regular set 1
01
*
∪ .
DFA and NFA
105
s 1
s 2
0
Start s 0
1
0
1
0,1
s 0
s 1
Start
s 2
0,1
1
0
s 0
s 1
s 2
0
1
0
0
1
s 1
s 2
s 3
0
0,1
1
0
Start s 0
1
0
0