Automata Theory 简明教程

Pushdown Automata Introduction

Basic Structure of PDA

下推自动机是一种以与我们为正规语法设计DFA类似的方式实现无上下文语法的途径。一个DFA可以记忆有限量的信息，而一个PDA可以记忆无限量的信息。

A pushdown automaton is a way to implement a context-free grammar in a similar way we design DFA for a regular grammar. A DFA can remember a finite amount of information, but a PDA can remember an infinite amount of information.

基本上，下推自动机为 −

Basically a pushdown automaton is −

"Finite state machine" + "a stack"

"Finite state machine" + "a stack"

一个下推自动机有三个组件 −

A pushdown automaton has three components −

  1. an input tape,

  2. a control unit, and

  3. a stack with infinite size.

栈头扫描栈的顶端符号。

The stack head scans the top symbol of the stack.

栈执行两种操作 −

A stack does two operations −

  1. Push − a new symbol is added at the top.

  2. Pop − the top symbol is read and removed.

一个PDA可以读取或不读取一个输入符号，但它必须在每个转换中读取栈的顶部。

A PDA may or may not read an input symbol, but it has to read the top of the stack in every transition.

pda

PDA 可以形式化描述为一个 7 元组 (Q, ∑, S, δ, q0, I, F)

A PDA can be formally described as a 7-tuple (Q, ∑, S, δ, q0, I, F) −

  1. Q is the finite number of states

  2. ∑ is input alphabet

  3. S is stack symbols

  4. δ is the transition function: Q × (∑ ∪ {ε}) × S × Q × S*

  5. q0 is the initial state (q0 ∈ Q)

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

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

下图展示了一个 PDA 从一个状态 q1 到状态 q2 的转换，标记为 a,b → c

The following diagram shows a transition in a PDA from a state q1 to state q2, labeled as a,b → c −

transition in a pda

这意味着在状态 q1 ，如果我们遇到一个输入字符串 ‘a’ 且栈顶符号是 ‘b’ ，则我们弹出 ‘b’ ，入栈 ‘c’ 至栈顶，并移至状态 q2 。

This means at state q1, if we encounter an input string ‘a’ and top symbol of the stack is ‘b’, then we pop ‘b’, push ‘c’ on top of the stack and move to state q2.

Terminologies Related to PDA

Instantaneous Description

PDA 的瞬时描述（ID）由三元组 (q, w, s) 表示，其中

The instantaneous description (ID) of a PDA is represented by a triplet (q, w, s) where

  1. q is the state

  2. w is unconsumed input

  3. s is the stack contents

Turnstile Notation

“turnstile”符号用于连接表示 PDA 的一次或多次移动的 ID 对。转换过程由 turnstile 符号“⊢”表示。

The "turnstile" notation is used for connecting pairs of ID’s that represent one or many moves of a PDA. The process of transition is denoted by the turnstile symbol "⊢".

考虑一个 PDA (Q, ∑, S, δ, q0, I, F)。一个转换可以用下面的 turnstile 符号以数学方式表示

Consider a PDA (Q, ∑, S, δ, q0, I, F). A transition can be mathematically represented by the following turnstile notation −

(p, aw, Tβ) ⊢ (q, w, αb)

这表示在从状态 p 转换到状态 q 时，消耗了输入符号 ‘a’ ，且栈顶 ‘T’ 被一个新字符串 ‘α’ 替换。

This implies that while taking a transition from state p to state q, the input symbol ‘a’ is consumed, and the top of the stack ‘T’ is replaced by a new string ‘α’.

Note - 如果希望 PDA 的移动次数为零或更多，则必须使用符号 (⊢*)。

Note − If we want zero or more moves of a PDA, we have to use the symbol (⊢*) for it.