[계산이론](21)[decidablity]

decidablity

애초에 답이 없는 문제를 풀기 위해 뻘짓을 하는 것만큼 낭비되는 일은 없다.

decidable

decider가 존재하는 language
    decider: loop없이 accept, reject로 결과를 내놓는 TM
    (계산이론 18 참고)
language가 decidable하다는 것은 problem이 decidable한 것을 보이는 것과 마찬가지이다.

 

다음은 deciable한 language(problem)의 예시이다.

 

A_DFA

$A_{DFA}$: 어떤 DFA(D)와 string(w)가 주어졌을 때, 이 DFA가 w를 accept할 지 판정하는 문제
    $A_{DFA}$ = {<D, w> | D is DFA that accepts input string w}
인코딩된 문자열이 주어졌을 때
    <D, w> = <$Q$, $\sum$, $\delta$, $q_0$, $F$, w>

1. TM 내부에서 w가 주어졌을 때 D를 시뮬레이션 한다
   내부 state, 현재 input char 등을 tape에 가록해가며 하면 된다.
2. 만약 D가 accept하면 TM도 accept, reject하면 reject한다

이떄, DFA는 accept, reject밖에 없으므로, TM은 decider이다
따라서, $A_{DFA}$는 decider가 존재하므로, decidable이다.

 

A_NFA

$A_{NFA}$: 어떤 NFA(N)와 string(w)가 주어졌을 때, 이 NFA가 w를 accept할 지 판정하는 문제
    $A_{NFA}$ = {<N, w> | N is NFA that accepts input string w}
인코딩된 문자열이 주어졌을 때
    <N, w> = <$Q$, $\sum_{\epsilon}$, $\delta$, $q_0$, $F$, w>

1. NFA N을 DFA D로 변환한다 ([[계산이론 정리 5]]참고)
2. TM 내부에서 w가 주어졌을 때 D를 시뮬레이션 한다
   내부 state, 현재 input char 등을 tape에 가록해가며 하면 된다.
3. 만약 D가 accept하면 TM도 accept, reject하면 reject한다

이떄, DFA는 accept, reject밖에 없으므로, TM은 decider이다
따라서, $A_{NFA}$는 decider가 존재하므로, decidable이다.

 

empty language test

DFA가 나타내는 language가 비어있음
    $E_{DFA}$ = {<A> | A is a DFA and L(A) = ∅}
    accept state가 없거나, accept state로 도달하지 못하거나
이건 이전에 connected graph인지 판정하는 TM으로 해결할 수 있다.
    start state에 .을 찍고
    연결된 state에도 .을 찍는다
    만약 어떤 accept state에도 .이 찍히지 않으면 empty set이다.

 

equivalent language test

두 DFA가 나타내는 language가 같음
    $EQ_{DFA}$ = {<A, B> | A and B are DFA and L(A) = L(B)}
이건 $(L(A)-L(B))\cup (L(B)-L(A)) = \emptyset$으로 판정한다
    $\iff (L(A)\cap \overline{L(B)})\cup(\overline{L(A)}\cap L(B))$
    $\iff \overline{(\overline{L(A)}\cup {L(B)})}\cup \overline{({L(A)}\cup \overline{L(B)})} = \emptyset$
DFA의 union은 예전에 regular expression할 때 배웠고...
$\bar{A}$는 reject와 accept를 뒤집으면 된다.

 

따라서 새로운 DFA C = $\overline{(\overline{A}\cup {B})}\cup \overline{({A}\cup \overline{B})}$에 대해 empty language check만 진행하면 된다.

 

A_CFG

$A_{CFG}$: 어떤 CFG와 string(w)가 주어졌을 때, 이 CFG가 w를 generate할 지 판정하는 문제
accept할 땐 유한번 연산 후 판정 가능
그러나, reject일떈 어떻게???
    accept하지 않으면 CFG는 멈추지 않음...
-> 유한번 연산될 수 있음을 보장하는 경계가 있나?

 

CFG가 chomsky normal form으로 주어진다면 최대 2n-1번의 연산을 하면 w를 generate할 수 있다.
    즉, 2n-1번의 단계를 거쳐도 w를 못 만든다면 reject하면 되고,
    loop는 없어지게 된다!

 

그리고, 모든 CFG는 chonsky normal form으로 변형할 수 있으므로,
$A_{CFG}$는 decidable하다.

 

CFL is decidable

단순히 PDA를 TM으로 바꾸면 PDA의 일부 loop 때문에 곤란할 수도 있다.
따라서 앞에서 보인 A_CFG를 이용해 증명하면 된다.

 

임의의 CFL A를 받았을 때 그에 대응되는 CFG G가 존재한다.
이떄 A_CFG에서 만든 TM에 <G, w>를 넣어
    단, w는 $\sum^{*}$의 임의의 문자열
accept면 accept, reject면 reject라고 한다.

• A_CFG와 CFL is decidable의 차이
  • A_CFG: w가 G로 generate될 수 있는가?
  • CFL... : w이 CFL이라면 결정 가능한가?

참고) 현재까지의 언어 계층구조
regular ⊆ context-free ⊆ decidable ⊆ turing-recognizable