Pushdown Automaton | 下推自动机

Definition | 定义

A Pushdown Automaton (PDA) is a type of computational model that extends the capabilities of a finite automaton by adding a stack. This additional stack allows the PDA to recognize a broader class of languages, specifically context-free languages. A PDA can be formally defined as a 7-tuple , where:

  • is a finite set of states.
  • is a finite set of input symbols (input alphabet).
  • is a finite set of stack symbols (stack alphabet).
  • is a transition function: .
  • is the initial state.
  • is the initial stack symbol.
  • is a set of accepting states.

下推自动机 (PDA) 是一种计算模型,通过添加堆栈来扩展有限自动机的能力。这个附加的堆栈使 PDA 能够识别更广泛的语言类别,特别是上下文无关语言。PDA 可以形式化定义为一个 7 元组 ,其中:

  • 是状态的有限集。
  • 是输入符号的有限集(输入字母表)。
  • 是堆栈符号的有限集(堆栈字母表)。
  • 是一个转换函数:
  • 是初始状态。
  • 是初始堆栈符号。
  • 是接受状态的集合。

Operations | 操作

A PDA can perform three types of operations based on the current state, the input symbol (which can include the empty string ), and the top symbol of the stack:

  1. Push: Add a symbol to the top of the stack.
  2. Pop: Remove the top symbol from the stack.
  3. No Operation (No-Op): Leave the stack unchanged.

PDA 根据当前状态、输入符号(可以包括空串 )和堆栈顶符号可以执行三种类型的操作:

  1. 入栈:将符号添加到堆栈顶部。
  2. 出栈:从堆栈中移除顶部符号。
  3. 无操作:堆栈保持不变。

Acceptance Criteria | 接受标准

There are two common criteria for a PDA to accept an input string:

  1. Acceptance by Final State: The PDA accepts an input string if, after reading the entire input, it reaches a final state in .
  2. Acceptance by Empty Stack: The PDA accepts an input string if, after reading the entire input, the stack is empty.

PDA 接受输入字符串有两种常见标准:

  1. 通过终止状态接受:如果 PDA 在读取整个输入后达到 中的一个终止状态,则接受该输入字符串。
  2. 通过空堆栈接受:如果 PDA 在读取整个输入后堆栈为空,则接受该输入字符串。

Example | 示例

Consider a PDA that recognizes the language . The PDA can be defined by the following components:

  1. States:
  2. Input Alphabet:
  3. Stack Alphabet:
  4. Initial State:
  5. Initial Stack Symbol:
  6. Accepting State:

The transition function can be described as follows:

This PDA pushes ‘A’ onto the stack for every ‘a’ in the input and pops ‘A’ for every ‘b’. If it successfully reaches the end of the input and the stack contains only the initial symbol ‘Z’, the input is accepted.

考虑一个识别语言 的 PDA。该 PDA 可以通过以下组件定义:

  1. 状态:
  2. 输入字母表:
  3. 堆栈字母表:
  4. 初始状态:
  5. 初始堆栈符号:
  6. 接受状态:

转换函数 可以描述如下:

该 PDA 在输入的每个 ‘a’ 时将 ‘A’ 推入堆栈,在每个 ‘b’ 时弹出 ‘A’。如果成功读取输入并且堆栈中仅包含初始符号 ‘Z’,则接受输入。