s Q
∈ is the start state,
t Q
∈ is the accept state, and
r Q
∈ is the reject state, r t
≠ .
25. What is a Mealey Machine?
Usually the finite automata have binary output i.e., they accept the
string or do not accept the string. This is basically decided on the basis
of whether the final state is reached by the initial state. Removing this
restrictin, we are trying to consider a model where the outputs can be
chosen from some other alphabet. The value of the output function F(t)
in the most general case is a function of the present state q(t) and present
input x(t).
F t
q t x t
( )
( ( ), ( ))
= λ
where λ is called the output function. This model is called the
“Mealey Machine”.
26. What is a Moore Machine?
If the output function F (t) depends only on the present state and is
independent of the present input q (t), then we have the output function
F(t) given by
F t
q t
( )
( ( ))
= λ
A Moore machine is a six-tuple ( , , , , , )
Q
q
Σ 0
0
δ λ
with the usual
meanings for symbols.
27. What is a regular set?
A set which is accepted by a finite automaton is called a regular set.
28. What is closure property of a regular set?
A set is closed under an operation if, whenever the operation is
applied to members of the set, the result is also a member of the set.
29. State the meanings of the following operations made on languages:
(a) L
L
1
2
∪
(b) L
L
1
2
∩
(c) – L 2 (d) L 1 – L 2 (e) L 1
*
(f) L
R
1 .
(a) L
L
1
2
∪ : Strings in either L 1 or L 2 .
(b) L
L
1
2
∩ : Strings in both L 1 and L 2 .
(c) – L 2 : All strings (over the same alphabet) not in L 1 .
(d) L 1 – L 2 : Strings in L 1 that are not in L 2 .
(e) L 1
* : Zero or more strings from L 1 concatenated together.
(f) L
R
1 : Strings in L 1 , reversed.
30. What is meant by Pumping Lemma?
The Pumping Lemma for regular languages is another way of
showing that a given infinite language is not regular.
31. What is the method of proof used by Pumping Lemma?
The proof is always done by contradiction.
112
Theory of Automata, Formal Languages and Computation
∈ is the start state,
t Q
∈ is the accept state, and
r Q
∈ is the reject state, r t
≠ .
25. What is a Mealey Machine?
Usually the finite automata have binary output i.e., they accept the
string or do not accept the string. This is basically decided on the basis
of whether the final state is reached by the initial state. Removing this
restrictin, we are trying to consider a model where the outputs can be
chosen from some other alphabet. The value of the output function F(t)
in the most general case is a function of the present state q(t) and present
input x(t).
F t
q t x t
( )
( ( ), ( ))
= λ
where λ is called the output function. This model is called the
“Mealey Machine”.
26. What is a Moore Machine?
If the output function F (t) depends only on the present state and is
independent of the present input q (t), then we have the output function
F(t) given by
F t
q t
( )
( ( ))
= λ
A Moore machine is a six-tuple ( , , , , , )
Q
q
Σ 0
0
δ λ
with the usual
meanings for symbols.
27. What is a regular set?
A set which is accepted by a finite automaton is called a regular set.
28. What is closure property of a regular set?
A set is closed under an operation if, whenever the operation is
applied to members of the set, the result is also a member of the set.
29. State the meanings of the following operations made on languages:
(a) L
L
1
2
∪
(b) L
L
1
2
∩
(c) – L 2 (d) L 1 – L 2 (e) L 1
*
(f) L
R
1 .
(a) L
L
1
2
∪ : Strings in either L 1 or L 2 .
(b) L
L
1
2
∩ : Strings in both L 1 and L 2 .
(c) – L 2 : All strings (over the same alphabet) not in L 1 .
(d) L 1 – L 2 : Strings in L 1 that are not in L 2 .
(e) L 1
* : Zero or more strings from L 1 concatenated together.
(f) L
R
1 : Strings in L 1 , reversed.
30. What is meant by Pumping Lemma?
The Pumping Lemma for regular languages is another way of
showing that a given infinite language is not regular.
31. What is the method of proof used by Pumping Lemma?
The proof is always done by contradiction.
112
Theory of Automata, Formal Languages and Computation