**一、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.

**二、語言操作的封閉性**

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

__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.

## 沒有留言:

## 張貼留言