Chapter
11: Decidability
Topics
Deciding whether a regular language is empty or not
Deciding whether two regular languages are the same
or not
We discuss two decidability questions here:
-
Is there an effective procedure (algorithm) for deciding whether
a regular language is empty?
-
Is there an effective procedure for deciding whether two regular languages
are the same language?
The answer to both questions is "yes".
Deciding
whether a regular language is empty or not
Construct the language’s FA. If no final state is reachable from the
start state, the language is empty. There is a procedure for determining
this:
I. If there are no final states, then the language is empty
II. Otherwise, do the following:
-
Place the start state into the (initially empty) collection R of reachable
states
-
If there is a final state in R, then the language is non-empty, and the
procedure is done, otherwise
-
Add to R all states having transitions to them from the states in R (eliminating
duplicates)
-
If no new states were added as a result of 3, then the language is empty,
and the procedure is done, otherwise
-
Repeat 2 and 3 and 4
Deciding
whether two regular languages are the same or not
Preparatory discussion:
Let L1 and L2 be the two languages.
| L1ÇL2¢=
those words in L1 but not in L2 |
L1¢ÇL2
= those words in L2 but not in L1 |
| if L1ÇL2¢=
Æ
then L1 Í L2 |
if L1¢ÇL2
= Æ then L2 Í
L1 |
|
If both are true, then L1 = L2
|
| We have the set-theoretic result: If (L1ÇL2¢)
È (L1¢ÇL2)
= Æ then
L1 = L2 |
By DeMorgan’s Law,
(L1¢ÈL2)¢
= (L1ÇL2¢)
and |
(L1ÈL2¢)¢
= (L1¢ÇL2) |
| so our result can be written: if (L1¢ÈL2)¢
È (L1ÈL2¢)¢
= Æ then L1
= L2 |
So, given languages L1 and L2:
-
we need only construct the FA for (L1¢ÈL2)¢
È (L1ÈL2¢)¢
(we know how to do this -- Chapter 9)
-
use the method described earlier to determine if it is empty
-
if so, the languages are the same
Here is a procedure to do this without building the FA for (L1¢ÈL2)¢È
(L1ÈL2¢)¢
in one big piece:
-
Build the FA for (L1¢ÈL2),
take its complement, and note if it accepts the empty language
-
Build the FA for (L1ÈL2¢),
take its complement, and note if it accepts the empty language
-
If the answer to 1 and 2 are both "yes", then (L1¢ÈL2)¢
È (L1ÈL2¢)¢
is empty, and L1 = L2
Example (Prob. 2, P. 217):
| L1 = language accepted by: |
L2 = language accepted by: |
 |
 |
Do L1ÈL2¢:
Transition table for L1ÈL2¢:
| state |
a |
b |
| 1 3 (final) |
2 4 |
1 5 |
| 2 4 (final) |
2 5 |
1 5 |
| 1 5 (final) |
2 4 |
1 5 |
| 2 5 (final) |
2 4 |
1 5 |
The FA for (L1ÈL2¢)¢
thus has no final states and (L1ÈL2¢)¢
= Æ
The FA for (L1¢ÈL2)¢
has the same transition table, and its states are also all non-final (you
do have to verify this), so (L1¢ÈL2)¢
= Æ
Therefore L1 = L2, and we are done!