計算理論 形式語言與自動機

Pushdown Automaton (PDA) is a kind of Automaton which comes under the theory of Computation that appoints stack. The word Pushdown stands due to the fact that the stack can be pushed down as operations can only work on the elements which are on the top of the stack. A PDA can store an infinite amount of information. It is used to identify Context-free languages.

下推式自動機(Pushdown Automaton，PDA)是一種基于計算理論的自動機，它指定堆棧。 之所以使用Pushdown一詞，是因為可以將堆棧向下推，因為操作只能在堆棧頂部的元素上進行。 PDA可以存儲無限量的信息。 它用于識別上下文無關的語言。

The following equation will help you to understand Pushdown Automaton (PDA),

以下等式將幫助您了解下推自動機(PDA) ，

"Pushdown Automation" = "Finite State Machine" + "Stack"

“下推式自動化” =“有限狀態機” +“堆棧”

A finite state machine does not employ any stack and only bothers about the input signal and the current state that does not work in the case of context free grammar. Push Down Automata is different from finite state machine because,

有限狀態機不使用任何堆棧，而只關心輸入信號和當前狀態，這在上下文無關文法的情況下不起作用。 下推自動機與有限狀態機不同，因為，

1. It uses top of the stack for deciding which transition is to be taken.

   它使用堆棧的頂部來決定要進行的過渡。

2. While performing the transition, it can handle or manipulate the stack.

   在執行過渡時，它可以處理或操縱堆棧。

Pushdown Automaton (PDA) reads the provided string from left to right direction. The current state, input symbol and the symbol at TOS (Top of the Stack) are being indexed in the table and helps in choosing a transition, this happens at each step. While performing a transition, PDA can manipulate stack in two ways, either it can push a symbol at the top of the stack or can pop out a symbol from the stack.

下推式自動機(PDA)從左到右讀取提供的字符串。 在表中為當前狀態，輸入符號和TOS(堆棧頂部)上的符號建立索引，并有助于選擇過渡，這在每個步驟中都會發生。 在執行轉換時，PDA可以通過兩種方式操縱堆棧，既可以將符號推入堆棧的頂部，也可以從堆棧彈出符號。

Formal definition of PDA,

PDA的正式定義，

PDA can be betokened formally by a 7-tuple (Q, ∑, S, δ, q0, I, F) where,

PDA可以由7個元組(Q，∑，S，δ，q0，I，F)正式標記，其中，

1. Q is the number of states. It is finite.

   Q是狀態數。 這是有限的。

2. ∑ is an input alphabet. It is a finite set.

   Σ是輸入字母。 這是一個有限集。

3. S stands for stack symbols.(which can be pushed and popped from the stack).

   S代表堆棧符號(可以從堆棧中壓入和彈出)。

4. δ is the transition function which is Q × (∑ ∪ {ε}) × S × Q × S*. It is a finite subset.

   δ是轉移函數Q×(∑ε{ε})×S×Q×S * 。 它是一個有限子集。

5. q0 is the start or initial or beginning state (q0 ∈ Q).

   q0是開始或初始或開始狀態(q0∈Q) 。

6. I is the initial stack top symbol (I ∈ S).

   I是初始堆棧頂部符號(I∈S) 。

7. F is the set of accepting states (F ∈ Q).

   F是一組接受狀態(F∈Q) 。

In a specified state, PDA will read the symbol which is at the top of the stack and the input signal and move to a new state after changing the symbol of the stack.

在指定狀態下， PDA將讀取堆棧頂部的符號和輸入信號，并在更改堆棧符號后移至新狀態。

Consider the following diagram which demonstrates transition in a PDA, from State q1 to state q2 described as x, y->z.

考慮下圖，該圖演示了PDA從狀態q1到狀態q2的過渡，描述為x，y-> z 。

In the above scenario, you can observe that if the current state of machine is q1, The input symbol is 'x' and 'y' is at the Top of Stack symbol then we can carry out push and pop operation by popping 'y' and pushing 'z' on the top of the stack and can proceed to state q2.

在上述情況下，您可以觀察到，如果計算機的當前狀態為q1 ，輸入符號為'x'并且'y'在堆棧頂部符號中，那么我們可以通過彈出'y'來執行推入和彈出操作并將'z'推入堆棧的頂部，然后可以進入狀態q2 。

Some important points of PDA:

PDA的一些要點：

• A PDA is used to check whether a given grammar is context free grammar or not.

  PDA用于檢查給定的語法是否為上下文無關的語法。

• A grammar is accepted if it reaches the end state on using of all its input symbols.

  如果語法在使用所有輸入符號時都達到結束狀態，則該語法被接受。

• There are some other notations of the PDA that are used. They are:

  使用了PDA的其他一些符號。 他們是：

  1. Instantaneous Description: For a PDA, instantaneous description is given by,即時描述 ：對于PDA，即時描述由，

  2.     triplet (q,w,s), where 
     q is the current state of the machine
     w is the set of input symbols that are remaining
     s is the stack. 
     
     

  3. Turnstile Notation: It defines the moves of PDA based on ID notation. Transition is defined as 旋轉記號 ：它根據ID記號定義PDA的移動。 過渡定義為'?'“?”

翻譯自: https://www.includehelp.com/toc/pushdown-automaton-pda-theory-of-computation.aspx

計算理論 形式語言與自動機