(c) (0 + 1)* represents the following:
(
)
(
) (
) (
)
*
*
0 1
0 1
0 1 0 1
+
= ∈ + + + +
+ +
=
LL Σ
(d) 0 represents the set { 0 }
(e) (
)
(
) (
)
{ }
*
*
0 1
0 1 0 1
+
= +
+
=
=
− ∈
+
+
Σ
Σ
18. What are the languages defined by the following regular expressions?
(a) ∅ (b) r r
1 2
(c) r r
1
2
+
(a) For ∅, the lan guage is { }
(b) For r r
1 2 , the language is L r L r
( ) ( )
1
2 .
(c) For r r
1
2
+ , the language is L r
L r
( )
( )
1
2
∪
.
19. Sketch the NFA for (a) x ∈ Σ (b) λ (c) ∅.
(a) NFA for x:
(b) NFA for λ:
(c) NFA for ∅:
20. What do you mean by two-way finite automata?
Two way-finite automata are machines that can read input string in
either direction.
21. What is the kind of arrangement you have for the “read head” in a
two-way automata machine?
These types of machines have a ‘read head’, which can move left or
right over the input string.
22. State a common characteristic between Finite automata and two-way
finite automata?
Both Finite automata and two-way finite automata have the same
finite set Q of states. They accept only regular sets.
23. What are the types of two-way finite automata?
(a) 2DFA (Deteministic)
(b) 2NFA (Non-deterministic)
24. Give the formal definition of a 2DFA (two-way DFA).
A 2DFA is an octuple
M
Q
s t r
= ( , , |–, –|, , , , )
Σ
δ
where, Q is a fine set of states,
Σ is a finite set of input,
|– is the left end marker, |– ∉ Σ ,
–| is the right end marker, –|∉ Σ ,
δ :Q
Q L R
× ∪
→
×
(
{|–, –|} (
{ , })
Σ
is the transition function
DFA and NFA
111
x
λ