Mathematical Foundation of Computer Science

DHARM

REGULAR AND NONREGULAR LANGUAGES 265

To answer the question let M = (Q, Σ δ, q 0 , F) be a DFA accepts language L, i.e. L = L(M),

then above problem may be stated as,

Is Empty (M)

Yes, if L(M) is Empty or L(M) = Ø;

No, if L(M) is Nonempty or L(M) Ø;¹

if L(M) = Ø⇒ Finite automata has no path between starting state and final state/s or there

is no way to reach to accepting state/s. Hence language is empty.

if L (M) ≠ Ø⇒There are one/more transition/s so that we can reach from starting state to

final state/s. hence language is nonempty.

FACT. If M be a DFA of n states, then L(M) is nonempty if and only if M accepts a string x

where | x | ≤ n.

To test the emptiness nature of the regular expressions, always remember following

points:

l Let r be a regular expression then if r = Ø or L(r) = Ø then it is empty.

l If r = r 1. Ø ⇒ r = Ø or L(r) = Ø then it is empty (whatever regular expressionr 1 is).

l If r = Ø + Ø ⇒ r = Ø or L(r) = Ø then it is empty.

l If r = r 1 * ⇒ L(r) contains at least a symbol that is ∈ (whatever the regular expres-

sion r 1 ) so it is never empty.

10.5.2(DP2)-Finiteness Problem

Let L is a regular language accepted by some finite automaton M then the question arises; Is
L(M) finite?
FACT. If M be a n states DFA then language L(M) is infinite if and only if M accepts a string
x s.t. n ≤ | x | < 2n.
From the pumping lemma of regular languages we see that if the language L (M) ac-
cepts any string of length ≥ Y n then L (M) is infinite because string can be written as u.v.w
where, | v | ≥ 1 and |u.v| ≤ n and ∀i ≥ 0, u.vi.w ∈ L (infinite many strings).
Prove the fact by contradiction:
Since L( M) is infinite, let a string x ∈ L of length at least 2n(| x | ≥ 2 n). Apply the pumping
lemma on x. So, x can be written as u. v. w s.t. | u. v | ≤ n and | v | ≥ 1.
Since | u. v. w | ≥ 2 n and | v | ≤ n ⇒ | u. w | ≥ n.
Further, | u. w | < | u. v. w |, because | v | ≥ 1.
Hence,
⇒ | u. w | ≥ n and | u. w | < | u. v. w |
⇒ n ≤ | u. w | < 2n [or 2n ≤ | u. w | < | x |]
Under this range there is no x ∈ L(M) or n ≤ | x | < 2n. So, it contradicts the assumption
of the string of length ≥ 2 n is in L.
Hence, if no strings of length less than 2n are accepted, then L(M) is finite, otherwise it
is infinite.