计算理论导引1正则语言.ppt

《计算理论导引1正则语言.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算理论第1章正则语言1主要内容1.1有穷自动机1.2非确定性1.3正则表达式1.4非正则语言本章小结作业21.1有穷自动机实际示例—自动门控制前缓冲区后缓冲区CLOSEDFRONTOPENNEITHERFRONTREARBOTHREARBOTHNEITHER控制器处于CLOSED状态，假设如下输入信号：FRONT,REAR,NEITHER,FRONT,BOTH,NEITHER,REAR,NEITHER,考察状态的变化。可以给出状态和信号之间的计算。3状态图q1q2q3100,101状态变换规则起始状态接

2、受状态4状态图q1q2q3100,101q1q2q2q3q2=“accept”oninput“1101”,themachinegoes:010:reject11:accept010100100100100:accept010000010010:reject:reject5有穷自动机的形式定义定义1.1有穷自动机是一个5元组(Q,,,q0,F)，其中(1)Q是一个有穷集合，称为状态集。(2)是一个有穷集合，称为字母表。(3):QQ是转移函数。(4)q0Q是起始状态。(5)FQ是接

3、受状态集。6有穷自动机举例例给定有穷自动机M1的状态图。请给出形式化的描述，并确定其能识别的语言。M1=({q1,q2,q3},{0,1},,q1,q2)L(M1)={w

4、w至少一个1并且在最后的1后面有偶数个0}q1q2q3100,101若A是机器M接受的全部字符串集，则称A是机器M的语言，记作L(M)=A，又称M识别A或M接受A。7有穷自动机举例例1.2给定有穷自动机M2的状态图。请给出形式化的描述，并确定其能识别的语言。q1q21001M2=({q1,q2},{0,1},,q1,q2)L(M2)

5、={w

6、w以1结束}8有穷自动机举例例1.3给定有穷自动机M3的状态图。请给出形式化的描述，并确定其能识别的语言。q1q21001L(M3)={w

7、w是空串或以0结束}9有穷自动机举例例1.4给定有穷自动机M4的状态图。请给出形式化的描述，并确定其能识别的语言。q1abaq2r1r2sbbababa10有穷自动机举例例1.5给定有穷自动机M5的状态图。请给出形式化的描述，并确定其能识别的语言。q020,q2q1001,2112,M5以模3的方式记录它在输入串中读到

8、的数字之和。11有穷自动机举例例1.6例1.5推广。对于每一个i>=1，设Ai是所有这种字符串的语言，其中数字之和是i的倍数。M=(Q,,,q0,F)Q={q0,q1,…,qn-1}(qj,0)=qj(qj,1)=qk,k=j+1modi(qj,2)=qk,k=j+2modi(qj,)=q0,k=j+1modi12计算的形式化定义定义1.7如果一个语言被一台有穷自动机识别，则称它是正则语言。设M=(Q,,,q0,F)是一台有穷自动机，w=w1w2…wn是一个字符串，并且wi是

9、字母表的成员。如果存在Q中的状态序列r0,r1,…,rn，满足下列条件：1)r0=q02)(ri,wi+1)=ri+1,i=0,1,…,n–1rnF则M接受w。13计算的形式化定义举例例1.8给定有穷自动机M5的状态图。令w是字符串1022012给出M5对w计算时进入的状态序列。q020,q2q1001,2112,14设计有穷自动机例：设计有穷自动机E1，假设字母表是{0,1}，识别的语言由所有含有奇数个1的字符串组成。qoddq

10、even101015设计有穷自动机例1.9设计有穷自动机E2，使其能识别含有001作为子串组成的正则语言。q001qq0q00010100,1116正则运算定义1.10设A和B是两个语言，定义正则运算并、连接和星号如下：并：A∪B={x

11、x∈A或x∈B}连接：AB={xy

12、x∈A且y∈B}星号：A*={x1x2…xk

13、k≤0且每一个xi∈A}17正则运算例1.11设字母表是标准的26个字母{a,b,…,z}。又设A={good,bad},B={boy,girl},求A∪B,AB和A*。18正则运算定

14、理1.12正则语言类在并运算下封闭。如果A1和A2是正则语言，则A1∪A2也是正则语言。设M1识别A1，M2识别A2。并设M1=(Q1,,1,q1,F1)和M2=(Q2,,2,q2,F2)构造识别A1∪A2的M=(Q,,,q0,F)Q=Q1Q2={(r1,r2)

15、r1Q1且r2Q2}((r1,r2),a)=(1(r1,a),2(r2,a))q0=(q1,q2)F={(r1,r2)

16、r1F1或r2F2