计算理论计算理论5章 文法与语言3
计算理论第五章自动机与语言下推自动机下推自动机﹙PDA﹚是一种抽象的计算模型。下推自动机比有限状态自动机复杂:比自动机多一个长度不受限制的栈.下推自动机下推自动机PDM定义:M=(Q,,,δ,q0,Z,F),其中:Q:有限状态集:栈符号集:输入符号集q0Q∈,初始状态Z:栈初始符号FQ,终止状态集δ:转换函数.下推自动机确定下推自动机:转换函数:Q×(×)Q×非确定下推自动机:转换函数:Q×(×)P(Q×)定理:确定下推自动机和非确定下推自动机不等价.例如下下推自动机M=({q0,q1,q2,q3},{a,b},{Z,a},δ,q0,Z,{...
2025-01-13
416.33KB 32 页 3
0
5玖币