This illustrates that uv w L
i
∈ , for all i ≥ 0.
Since uv a a
a k
= 1 2 KK
and
k n uv n
≤
≤
, | | .
Hence, | | .
v ≥1
¨
THE O REM: The set of strings that is accepted by a finite automaton which has
‘n’ state is
(a) nonempty if and only if M accepts some string of length less than
n.
(b) infinite, if an only if M accepts some string of length k where
n k
n
≤ < 2 .
Thus there is a DECISION ALGORITHM, to find out whether M accepts
zero, a finite number, or an infinite number of strings.
Algorithm (i): Let us give an algorithm to decide if T M
( )
.
= ∅
Let us consider the strings of length less than n. Test if any of these strings
is in T(M). If so, T M
( )
.
= ∅ Otherwise, T(M) is empty.
Algorithm (ii): Let us give an algorithm to decide if T(M) is infinite.
Let us consider the strings of length k, where n k
n
≤ ≤ −
2 1. Test if any
such string is found in T(M). If so, T(M) is infinite, otherwise T(M) is finite.
Ì Exam ple 3.4.1: Prove that there exists an algorithm to find if two finite
automata M 1 and M 2 accept the same language.
Proof: Let us assume that
L T M
L
T M
1
1
2
=
=
( )
(
).
and
2
Let us define L L L
L L
=
−
∪
−
(
) (
).
1
2
2
1
The language L is regular.
Let us assume that M is a finite automaton such that L = T(M).
Now, if L = ∅, iff L L
1
2
= .
Since there is an algorithm (decision algorithm) to test if L is a empty, we
have an algorithm to check if L 1 = L 2 .
¨
Ì Exam ple 3.4.2: Check whether the language defined by
L a
p
p
=
=
{
is a prime number} is regular or not.
Pushdown Automata
177