Formal Language - Ch12.5 決定與不可決定問題相關習題

一、k-PDA的計算能力
一個有限狀態機賦予不同k個堆疊會具有不同的計算能力，而其計算能力結論為：
0-PDA(DFA) < 1-PDA (傳統PDA) < 2-PDA = 3-PDA = 4-PDA = 5-PDA = ......


1.1   Let a k-PDA be a pushdown automaton that has k stacks. Thus a 0-PDA is an NFA and 1-PDA is a conventional PDA. You already know that 1-PDAs are more powerful (recognize a larger class of languages) than 0-PDAs. So, 2-PDAs are more powerful than 1-PDAs.

Consider the language $L = \{a^nb^nc^n:n ≥ 0\}$. We already know that this is not a CFL; hence, the standard 1-PDA cannot accept L.

However, a 2-PDA can accept L by storing a’s on one stack, b’s on the other, and then popping one a and one b for each remaining c of the input. If both stacks are empty after the last c is read, then w is accepted.

1.2   3-PDAs and 2-PDAs have the same power. 

We show that two stacks can simulate a TM, an extra stack does not lead to a more powerful automaton. The extra stack can easily be presented by another tape on the TM. Any k-tape TM is equivalent to a single tape TM, therefore 3- PDAs and 2-PDAs are equivalent in power.

The TM by 2-PDA simulation is done as follows:

• Stack 1 would represent the tape contents to the left of the current head position of the TM
• Stack 2 would be the tape contents to the right of the current head position with the current symbol on the top of the stack. 

The two stack contents would change accordingly as the head moved across the tape left or right.



二、語言操作的封閉性
通常會考差集和補集，因為這兩個操作在可決定語言內有封閉性，而在可識別語言裡卻沒有。

2.1   The class of decidable languages is closed under complement.
Proof: Let M be a TM that decides a language L. Construct a TM M′ that decides L in the following way:

M′ = “On input w:
     1. Simulate M on w.
     2. Accept if M rejects, reject if M accepts”.

[用心去感覺] for decidability we always have to check two things –

• M′ always halts,
• M′ gives the correct result on every input.

2.2   The class of Turing-recognizable languages is "not" closed under complement.

Let M the TM accepting a Turing-recognizable language L. Now assume by contradiction that L', the complement of L, is also Turing-recognizable.This means that there exists a TM M' that recognizable all the elements in L'.

Now we can run M and M' in parallel and output YES if M halts, and NO if M' halts. Notice that since both L and L' are Turing-recognizable so guarantee to halt. But this means that L is decidable which contradicts the fact that the halting problem (ATM) is undecidable but Turing-recognizable.

三、其他題目

3.1   Let A and B be two disjoint languages. Say that language C separates A and B if A ⊆ C and B ⊆ C. Show that any two disjoint co-Turing-recognizable languages are separable by some decidable language.

Ans: Let A and B be two co-turing-recognizable languages. By definition, there exists turing machines that recognizes the complement of these languages, let us call these: TM $M_{A'}$ and $M_{B'}$. Note that $L(M_{A'}) = A'$ and $L(M_{B'}) = B'$. Also assume that $A \cap B = \phi \leftrightarrow A' \cup B' = \Sigma^*$

The proof is by constructing a machine M, which is a decider and separates A and B. Such machine works as follow:

M = on input w :

1. Run both machines $M_{A'}$ and $M_{B'}$ in parallel on input w. 

2. If $M_{B'}$ accepts w, accept.

3. If $M_{A'}$ accepts w, reject.

From the preliminaries we know that any string in Σ∗ is either on A' or B'. Machine M uses recognizers for A' and B' and thus, will halt on every input, i.e., it is a decider.

Moreover, because A and B are disjoints, any string in A is in B'. It follows that L(M) = C is a decider that separates A and B.