Decidability 02
Thumrongsak Kosiyatrakul
[email protected]
Thumrongsak Kosiyatrakul
[email protected]
Decidability 02

Decidable Languages
E
DFA
Let
E
DFA
=
{h
A
i |
A
is a DFA and
L
(
A
) =
∅}
. Show that
E
DFA
is decidable.
How do we know a DFA accepts no string?
This machine has no accept state (
F
=
∅
) or
This machine has some accept states but are not reachable
from the start state
To show that
E
DFA
is decidable, we need a Turing machine
T
such that
If
h
A
i ∈
E
DFA
,
T
accepts
h
A
i
If
h
A
i 6∈
E
DFA
,
T
rejects
h
A
i
Thumrongsak Kosiyatrakul
[email protected]
Decidability 02

Not a Decider Example
Consider this TM
S
:
S
=
“On input
h
A
i
where
A
is a DFA:
1
For all strings
w
:
2
Run TM
M
on input
h
A, w
i
3
If
M
accepts
h
A, w
i
,
reject
”
Do you see the problem of TM
S
?
TM
S
is not a decider
Given
h
A
i
where
A
is a DFA and
L
(
A
) =
∅
,
S
will run
indefinitely
For this problem:
We may have to play around with its state diagram
Create a Turing machine that analyze a DFA by marking all
states reachable from the start state. If no accept state is
marked, the DFA accepts no string
Thumrongsak Kosiyatrakul
[email protected]
Decidability 02

Decidable Languages
Consider the following TM
T
:
T
=
“On input
h
A
i
, where
A
is a DFA:
1
Mark the start state of
A
.
2
Repeat until no new states get marked:
3
Mark any state that has a transition coming into it from
any state that is already marked.
4
If no accept state is marked,
accept
; otherwise,
reject
.”
We should not need to go down to the state diagram of a
DFA unless it is necessary
Rely on graph theory
To prove, it must be based on graph theory
Thumrongsak Kosiyatrakul
[email protected]
Decidability 02

Decidable Languages
EQ
DFA
Let
EQ
DFA
=
{h
A, B
i |
A
and
B
are DFAs and
L
(
A
) =
L
(
B
)
}
.
Show that
EQ
DFA
is decidable.
Given two DFAs
A
and
B
, is there any algorithm to check
whether
L
(
A
) =
L
(
B
)
?