(15)第二章-第八讲-双向和有输出的有限自动机VIP

第二章

有限自动机和右线性文法

第八讲

双向和有输出的有限自动机一、双向有限自动机

本章第一讲中介绍的有限自动机的输入带上的读头只能从左向右移动，每输入一个字符读头就向右移动一格。

所谓双向有限自动机是指每输入一个字符时输入带上的读头既可以往左移动，也可以往右移动，甚至于不移动。本讲不讨论不移动的情况。一、双向有限自动机

M=(Q,T,δ,q0,F),其中：

例如：

δ(q1,a)={q2,L}表明当读入字符a时2DFA的状态从q1转换到q2，且读头往左移动一格；1.

确定的双向有限自动机

(2DFA)M的形式定义

与DFA相比，只有转换函数δ不同：δ：是从Q×T到Q×{L,R}的映射。

δ(q1,a)={q2,R}则表明当读入字符a时2DFA的状态从q1转换到q2，且读头往右移动一格；一、双向有限自动机2.

用“格局”描述2DFA的瞬时变化重要回顾：原始的有限自动机中格局的定义：定义2

设有限自动机M=(Q,T,δ,q0,F),

对偶(q,w)∈Q×T*称为M的格局，并称(q0,w)为初始格局；对于q∈F,称(q,ε)为终止格局或接受格局。

若当前状态为q，当前读入字符为a，若有状态转换函数δ(q,a)=q1,则状态变换后的后继状态为q1，此时可用格局变化形式描述这一变换过程：(q,aw)├─(q1,w)。一、双向有限自动机

格局形式：w1qw2w1w2

∈T*,q∈Q其中：w1w2

是输入字符串w,w1

是当前读头左边的字符串部分,w2是当前读头右边的字符串部分,q是当前状态,在格局中的位置亦表示输入带上读头的位置。2.

用“格局”描述2DFA的瞬时变化

当w2=ε时，则表示读头已达到输入字符串w的最右边。

格局变化：当格局为b1b2...bmq1bm+1...bn时，若有：

δ(q1,bm+1)=(q2,R),则有：b1b2...bmq1bm+1...bnb1b2...bmbm+1q2bm+2...bn

,一、双向有限自动机

对于一个确定的双向自动机M而言，它所接受的字符串w是在初始状态q0时，从输入字符串w的最左字符开始逐个读入字符(中间可能经过读头的左右移动而使某些字符被多次读取)，直至最后读头移动到w的右边且恰好进入终止状态，则称w被2DFAM所接受。3.2DFA所接受的句子及其所定义的语言

2DFAM所接受的句子的集合称为2DFAM所定义的语言。记为：L(M)={w|q0w

wq,q∈F}一、双向有限自动机实例：设2DFAM=（{q0,q1,q2},{a,b},δ,q0,{q1})其中转换函数δ如下：δ(q0,a)=(q0,R),δ(q0,b)=(q1,R),δ(q1,a)=(q1,R),δ(q1,b)=(q2,L),δ(q2,a)=(q0,R),δ(q2,b)=(q2,L),则当输入字符串序列babaa时，其格局序列为：

q0babaababq1aa

此时，读完所有字符并进入q1状态，且q1∈F是结束状态，故知字符串babaa被M所接受。bq1abaabaq1baabq2abaabaq0baababaq1ababaaq1二、有输出的有限自动机

有输出的自动机是有限自动机的另一种类型，这类自动机当有字符输入时不仅有状态转换，同时会引起字符的输出。常见的有输出的自动机有米兰机和摩尔机。米兰机：输出字符不仅与它所处的状态有关，而且还与输入字符有关。摩尔机：输出字符仅与它所处的状态有关，而与输入字符无关。二、有输出的有限自动机1.米兰机的形式定义定义：设有限自动机M为一个六元组,M=(Q,T,R,δ,g,q0),其中：(1)Q是有限状态集合;则称M为米兰机。(2)T是有限输入字母表

;(3)R是有限输出字母表

;(4)δ是状态转换函数，是从Q×T到Q的映射；(5)g是输出函数，是从Q×T到R的映射；(6)q0是初始状态，q0∈Q；注意：米兰机无所谓终止状态，它的任务主要是要得到输出字符串二、有输出的有限自动机2.

米兰机工作状况的描述可以使用状态转换函数δ和输出函数g来描述米兰机工作状况的瞬时变化。例如：当转换函数为δ(q,a)=p时，表明在状态q，输入字符为a时，M转换到状态p，此时g(q,a)=b表示输出字符b。用状态图表示这个工作状况，则是从q到p有一条标有a/b的弧，a是输入字符，b是输出字符。输出字符b依赖于当前状态q和当前的输入字符aqpa/b二、有输出的有限自动机3.

米兰机的应用举例例1：设计一个米兰机M=(Q,T,R,δ,g,q0),它的输出是输入字符个数的模3值。

②由于任何正整数对3的模运算的结果只可能是：0,1,2，所以输出字母表R设为{0,1,2}；解：

①由于输出仅与输入字符的个数有关，故可设输入字母表T只有一个字符a；

④根据题意，状态转换函数δ和输出函数g定义如下：

δ(q0,a)=q1δ(q1,a)=q2

δ(q2,a)=q0

g(q0,a)=1

g(q1,a)=2g(q2,a)=0

③由于M要记住当前已经输入的字符个数的模3值，故可设3个不同状态q0,q1,q2来记忆这3种不同状态。例1：设计一个米兰机M=(Q,T,R,δ,g,q0),它的输出是输入字符个数的模3值。

②由于任何正整数对3的模运算的结果只可能是：0,1,2，所以输出字母表R设为{0,1,2}；解：

①由于输出仅与输入字符的个数有关，故可设输入字母表T只有一个字符a；

④根据题意，状态转换函数δ和输出函数g定义如下：

δ(q0,a)=q1δ(q1,a)=q2

δ(q2,a)=q0

g(q0,a)=1

g(q1,a)=2g(q2,a)=0

③由于M要记住当前已经输入的字符个数的模3值，故可设3个不同状态q0,q1,q2来记忆这3种不同状态。例1：设计一个米兰机M=(Q,T,R,δ,g,q0),它的输出是输入字符个数的模3值。

②由于任何正整数对3的模运算的结果只可能是：0,1,2，所以输出字母表R设为{0,1,2}；解：

①由于输出仅与输入字符的个数有关，故可设输入字母表T只有一个字符a；

④根据题意，状态转换函数δ和输出函数g定义如下：

δ(q0,a)=q1δ(q1,a)=q2

δ(q2,a)=q0

g(q0,a)=1

g(q1,a)=2g(q2,a)=0

③由于M要记住当前已经输入的字符个数的模3值，故可设3个不同状态q0,q1,q2来记忆这3种不同状态。故Q={q0,q1,q2}故有：M=({q0,q1,q2},{a},{0,1,2},δ,g,q0)其转换图如右所示：q0q1q2a/1a/2a/0当输入字符串为aaaaa时，M的动作为：q0→q1→q2→q0→q1→q2,输出字符串为:12012状态序列为:q0q1q2q0q1q2a/1a/2a/0a/1a/2二、有输出的有限自动机4.摩尔机的形式定义定义：设有限自动机M为一个六元组,M=(Q,T,R,δ,g,q0),其中：(1)Q是有限状态集合;则称M为摩尔机。(2)T是有限输入字母表

;(3)R是有限输出字母表

;(4)δ是状态转换函数，是从Q×T到Q的映射；(5)g是输出函数，是从Q到R的映射；(6)q0是初始状态，q0∈Q；注意：摩尔机也无所谓终止状态，它的任务主要也是要得到一个输出字符串。二、有输出的有限自动机5.

摩尔机工作状况的描述与米兰机一样，可以使用状态转换函数δ和输出函数g来描述摩尔机工作状况的瞬时变化。例如：当转换函数为δ(q,a)=p时，表明在状态q，输入字符为a时，M转换到状态p，此时g(p)=b表示当达到状态p时输出字符b。用状态图表示这个工作状况，则是从q到p有一条标有a的弧，而各状态中的字符（如b1或b2）则表示达到该状态时M的输出字符。输出字符b仅依赖于当前状态p。q,b1p,b2ax1x2x3x4二、有输出的有限自动机6.

摩尔机的应用举例例1：设计一个摩尔机M=(Q,T,R,δ,g,q0),它的输入字符串w是0,1组成的；输出值是w中1的个数减0的个数的模4值。

②由于任何正整数对4的模运算的结果只可能是：0,1,2,3,所以输出字母表R设为{0,1,2,3}；解：①由于输入字符为0或1，故可设输入字母表T为{0,1}；

④根据题意，状态转换函数δ和输出函数g定义如下：

δ(q0,0)=q3δ(q1,0)=q0

δ(q2,0)=q1δ(q3,0)=q2

g(q0)=0

g(q1)=1g(q2)=2g(q3)=3

③由于M要记住的当前已经输入的1的个数和0的个数的差的模4值，故可设4个不同状态q0,q1,q2,q3来记忆这4种不同状态。

δ(q0,1)=q1δ(q1,1)=q2

δ(q2,1)=q3δ(q3,1)=q0例1：设计一个摩尔机M=(Q,T,R,δ,g,q0),它的输入字符串w是0,1组成的；输出值是w中1的个数减0的个数的模4值。

②由于任何正整数对4的模运算的结果只可能是：0,1,2,3,所以输出字母表R设为{0,1,2,3}；解：①由于输入字符为0或1，故可设输入字母表T为{0,1}；

④根据题意，状态转换函数δ和输出函数g定义如下：

δ(q0,0)=q3δ(q1,0)=q0

δ(q2,0)=q1δ(q3,0)=q2

g(q0)=0

g(q1)=1g(q2)=2g(q3)=3

③由于M要记住的当前已经输入的1的个数和0的个数的差的模4值，故可设4个不同状态q0,q1,q2,q3来记忆这4种不同状态。

δ(q0,1)=q1δ(q1,1)=q2

δ(q2,1)=q3δ(q3,1)=q0例1：设计一个摩尔机M=(Q,T,R,δ,g,q0),它的输入字符串w是0,1组成的；输出值是w中1的个数减0的个数的模4值。

②由于任何正整数对4的模运算的结果只可能是：0,1,2,3,所以输出字母表R设为{0,1,2,3}；解：①由于输入字符为0或1，故可设输入字母表T为{0,1}；

④根据题意，状态转换函数δ和输出函数g定义如下：

δ(q0,0)=q3δ(q1,0)=q0

δ(q2,0)=q1δ(q3,0)=q2

g(q0)=0

g(q1)=1g(q2)=2g(q3)=3

③由于M要记住的当前已经输入的1的个数和0的个数的差的模4值，故可设4个不同状态q0,q1,q2,q3来记忆这4种不同状态。

δ(q0,1)=q1δ(q1,1)=q2

δ(q2,1)=q3δ(q3,1)=q0

②由于任何正整数对4的模运算的结果只可能是：0,1,2,3,所以输出字母表R设为{0,1,2,3}；解：①由于输入字符为0或1，故可设输入字母表T为{0,1}；

④根据题意，状态转换函数δ和输出函数g定义如下：

δ(q0,0)=q3δ(q1,0)=q0

δ(q2,0)=q1δ(q3,0)=q2

g(q0)=0

g(q1)=1g(q2)=2g(q3)=3

③由于M要记住的当前已经输入的1的