(b)
(c)
(d)
(e)
(i) ∈ +
+
0 01 1 00 01
(
) ( )
*
*
*
(ii) ∈ +
+
0 10 1 10 10
(
)
*
*
*
(iii) ∈ +
+
0 10 1 00 0
(
)
*
*
(iv) ∈ +
+
0 01 1 00 0
(
)
*
*
(v) ∈ +
+
0 10 1 10 1
(
)
*
*
48. Define an NFA with four states equivalent to the regular expression
(
)
*
01 011 0111
+
+
.
Convert this automaton to an equivalent deterministic one.
49. Obtain the DFA equivalent to the following regular expressions:
(a) (00 + 11)
* (01 + 10) (00 + 11)
*
(b) (000)
* 1 + (00)
* 1
(c) (0 (01)
* (1 + 00) + 1 (10)
* (0 + 11))
*
SHORT QUESTIONS AND ANSWERS
1. What is an automaton?
An Automaton is an abstract model of a digital computer. It has a
mechanism to read input, which is a string over a given alphabet. This
input is actually written on an “input” file, which can be read by the
automaton but cannot change it.
2. What are the types of Automaton?
(a) Deterministic Automata
108
Theory of Automata, Formal Languages and Computation
q 0
q 1
q 2
1
0
1
0
1
q 0
q 1
q 2
0
0
0
1
1
q 0
q 1
q 2
0
0
1
1
1
q 0
q 1
q 2
0
0
1
0
1