自动机与文法7 下推自动机

第七讲

下推自动机

下推自动机的基本概念

下推自动机的语言：两种定义

两种定义的等价性下推自动机

下推自动机（pushdownautomaton）是带有一个堆栈的有限状态自动机.下推自动机的基本概念

有限状态集

有限输入符号集

有限堆栈符号集

转移函数

一个开始状态

一个开始堆栈符号

终态集合q0

Q

Z0

F

Q:Q(

)

2Q*

形式定义一个下推自动机PDA是一个七元组

P=(Q,

,

,

,q0,Z0,F).

下推自动机的基本概念

举例

所接受语言为L=0n1n

n

1

的一个PDA

P=({q0,q1,q2},

{0,1},{X,Z0},

,q0,Z0,{q2})

其中，转移函数定义如下

(q0,0,Z0)={(q0,XZ0)},(q0,0,X)={(q0,XX)},(q0,1,X)={(q1,)},(q1,1,X)={(q1,)}(q1,

,Z0)={(q2,Z0)}

对其余的参数值，

(q,a,Y)=下推自动机的基本概念

举例

上述PDA如何接受输入字符串？例如，00001111.Z0stack当前状态:q0q0q0q0XXXq0X下推自动机的基本概念

举例

上述PDA如何接受输入字符串？例如，00001111.Z0stack当前状态:XXXq1下推自动机的基本概念

举例

上述PDA如何接受输入字符串？例如，00001111.Z0stack当前状态:XXq1下推自动机的基本概念

举例

上述PDA如何接受输入字符串？例如，00001111.Z0stack当前状态:Xq1下推自动机的基本概念

举例

上述PDA如何接受输入字符串？例如，00001111.Z0stack当前状态:q1下推自动机的基本概念

举例

上述PDA如何接受输入字符串？例如，00001111.Z0stack当前状态:q2下推自动机的基本概念

用ID（instantaneousdescriptions）表达当前格局

PDA的当前格局用三元组（q,w,

）表示，称为ID，其中

q为当前状态，w为剩余的输入串，

为当前栈中的内容.

设PDAP=(Q,

,

,

,q0,Z0,F)，定义ID

推导关系├P（在不至于混淆时用├表示）为

（q,aw,X

）├

（p,w,

）iff

(p,

)

(q,a,X)，其中p,q

Q，a

，w*

，X

，

,*.

上述ID推导关系的自反传递闭包├*P（或├*）定义为

基础对任意IDI,I├*I

.

归纳对任意IDI,J,K,如果I├K,K├*J,则I├*J.下推自动机的语言：两种定义下推自动机的语言：两种定义

举例

下图PDA接受输入串000111的ID

推导过程.

结论

设PDAP=(Q,

,

,

,q0,Z0,F)，如果（q,x,

）├*

（p,y,

），则对任何w*

和

*，

（q,xw,

）├*

（p,yw,

）.

证明思路：归纳于（q,x,

）├*（p,y,

）的步数.（q0,000111,Z0）├*（q0,111,XXXZ0）├*（q1,

,Z0）├*（q2,

,Z0）

终态接受的定义方法设PDAP=(Q,

,

,

,q0,Z0,F)，定义L(P)={w

(q0,w,Z0)├*（q,

,

）},其中q

F,

*.

空栈接受的定义方法设PDAP=(Q,

,

,

,q0,Z0)，定义N(P)={w

(q0,w,Z0)├*（q,

,

）},其中q

Q.

举例所接受语言为N(P)=0n1n

n

1

的一个PDA

P=({q0,q1},

{0,1},{X,Z0},

,q0,Z0)

其中，转移函数定义如下

(q0,0,Z0)={(q0,XZ0)},(q0,0,X)={(q0,XX)},(q0,1,X)={(q1,)},(q1,1,X)={(q1,)}(q1,

,Z0)={(q1,)}，对其余的参数值，

(q,a,Y)=下推自动机的语言：两种定义

从空栈接受到终态接受设PDAPN=(Q,

,

,

N,q0,Z0),L=L(PN),则存在PDAPF

,满足L=L(PF).

证明思路：PF=(Q

{p0,pf},

,

{X0},

F,p0,X0,{pf}

)两种定义的等价性

从终态接受到空栈接受设PDAPF=(Q,

,

,

F,q0,Z0,F

),L=L(PF),则存在PDAPN

,满足L=N(PN).

证明思路：PN=(Q

{p0,p

},

,

{X0},

N,p0,X0)两种定义的等价性课后练习

必做题:Ex.6.2.1(b),(c)Ex.6.2.6

思考题:

!Ex.6.2.2(b)

自测题:试构造接受下列语言的一个PDA（空栈接受或终态接受均可）：

1）

L={w

w

{a,b}*,且w

的任何前缀中a

的数目至少2倍于b

的数目}2）L={w

w

{a,b}*,且w

中

a的数目不等于

b的数目}3）L={w

w

{a,b,c}