自然语言处理（四）——下推自动机所接受的语言

一、概念

我们可以将不确定PDA的形式化定义为一个七元素集合：M = (Σ, Q, Γ, δ, q0, Z0, F) 其中Σ代表输入符号表，并且是有限集合；Q表示状态空间，并包含初始状态q0；Γ表示栈符号表，并且是有限集合；δ是从Q×(Σ∪{ε})×Γ到Q×Γ*的一个映射函数；Z0属于Γ，并且是栈最顶端最初存在的起始符号；F是由终止状态构成的状态子集。

映射关系δ(q,a,Z)定义为{(q₁,y₁),(q₂,y₂),…,(qₘ,yₘ)}其中状态q_i属于集合Q输入符号a属于字母表Σ栈顶符号Z属于Γ生成序列y_i属于Γ*这一规则表明：当PDA处于状态q并面临输入符号a时自动机将转至状态q_i(i=1、2、…、m)并将当前栈顶符号Z替换为生成序列y_i随后使读头指向下一个字符位置每当当前栈顶符号为Z时生成序列y_i中的每个字符y_j(j=1、2、…、k)都将依次被压入栈中形成从下而上的排列

在某些特定情况下，在δ(q, ε, Z)={(q1, γ1), (q2, γ2), …,(qm ,γm)}时，在输入读头位置不变的情况下，并且仅用于执行下推栈内部的操作时，则称这种情况为"ε移动"。

我对这些定义的理解迅速达到了瓶颈。这部分内容通过图形化展示的方式得以呈现：下推自动机相较于有限自动机主要增加了下推存储器这一组件。

![](https://cdl.itadn.