“下推自动机”的意思、由来-中文百科全书

词条

下推自动机

释义

§ 因素

PDA的动作由三个因素决定:（1）当前所处状态；

（2）读头所指符号；（3）下推栈栈顶符号。

定义：PDA定义为一七元组

M=（Q，，H，，q0，z0，F），其中：

Q为控制器的有穷状态集；

是一个有穷字母表；

q0Q是控制器的初始状态；

H是下推字母表；

Z0H是下推栈的初始符；

FQ是一终止状态集；

是转换函数，是在 Q（{}）HQH*的映射。转换函数为：

（q，a，z）={（q1，1），（q2，2），…（qn，n）}

其中q，qiQ，a*，zH。其意义是，控制器当前状态为q，下推栈栈顶符号为z，输入符号为a（可为）情况下，状态转换到序偶集。这个序偶集由（qi，i）组成，其中qi下一状态，i为代替z的栈顶符号串，注意要用i的逆串放入栈中。

推自动机和上下文无关文法

设有文法G【A】：

AA（A）

不难看出该文法对应的语言是成对括号串的集合，如

（），（（）），（）（），（（）（））（），（（）（（）））……

能识别该文法定义的语言的自动机为：

( 　　　 ( 　　　　 ( 　　　　　 (

S0 　　　　　 S1 　　　　 S2 　　　　　 …. 　　　　　　 Sn

) 　　　 ) 　　　　 ) 　　　　　 )

显然该自动机只能识别嵌套层数为K的成对括号串，若增加了一层嵌套，则需要在自动机的右端增加一个新的状态，随着嵌套层次的增加，状态要增加

随便看

百科全书收录594082条中文百科知识，基本涵盖了大多数领域的百科知识，是一部内容开放、自由的电子版百科全书。