资源描述：
《编译原理 教学课件 作者 王生原 董渊 杨萍 张素琴 slide03.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、文法/正规式/有限自动机─基础知识第三讲形式语言概念正规语言及其描述文法/正规式/有限自动机─基础知识上下文无关文法及语言形式语言概念字母表（Alphabet）形式符号的集合常用表示举例英文字母表a,b,…,z,A,B,…,Z汉字表…,自,…,动,…,机,…化学元素表H,He,Li,…,Une=a,n,y,任,意形式语言概念字符串（String）字母表上的一个字符串（串），或称为字（word），为中字符构成的一个有限序列。空串（emptystring）,常用表示，不包含任何字符。字符串
2、w的长度，记为w，是包含在w中字符的个数举例=0，bbaba=5形式语言概念字符串的连接（concatenation）运算设x,y为串,且xa1a2…am,yb1b2…bn,则x与y的连接xya1a2…amb1b2…bn连接运算的性质(xy)zx（yz）xxxxyx+y形式语言概念字母表上的运算幂运算设为字母表，n为任意自然数，定义（1）0=（2）设xn-1，a，则axn（3）n中的元素只能由（1）和（2）生成闭包*=012…闭
3、包+=123…形式语言概念语言（Languages）概念设为字母表，则任何集合L*是字母表上的一个语言举例…,English,…,words,…any,任意比较空语言与仅含空字的语言形式语言概念语言上的运算两个语言L和M的联合（union）LM=wwLwM两个语言L和M的连接（concatenation）L·M=w1w2w1Lw2M语言L的闭包（closure）L*=L0L1L2…=i0Li,其中L0=，L1=L,L2=LL,…Ln
4、=Ln-1L形式语言概念程序设计语言C源程序的集合用*表示（为ASCII字符集）L表示由满足C语言词法规则的单词构成的语言M表示由满足C语言语法规则的源程序构成的语言S表示由正确的C语言源程序构成的语言四者之间的关系L*，M*，S*ML*,SL*SM形式语言概念几个重要的形式语言类正规语言及其描述描述正规语言的形式工具3型（正规）文法有限自动机正规表达式有限自动机的五要素有限状态集有限输入符号集转移函数一个开始状态一个终态集合q0q1q2q3正规语言及其描述有限状态集有限输入符号集转移函数
5、一个开始状态一个终态集合一个确定有限状态自动机DFA(deterministicfiniteautomata)是一个五元组A=(Q,,,q0,F).:QQq0QFQ确定有限自动机的形式定义正规语言及其描述Q={q0,q1,q2,q3}={0,1}(q0,0)=q2,(q0,1)=q1(q1,0)=q3,(q1,1)=q0(q2,0)=q0,(q2,1)=q3(q3,0)=q1,(q3,1)=q2q0F={q0,q3}q0q1q2q3转移图表示的DFA正规语言及其描述q0q1q
6、2q301q2q1q3q0q0q3q1q2Q={q0,q1,q2,q3}={0,1}(q0,0)=q2,(q0,1)=q1(q1,0)=q3,(q1,1)=q0(q2,0)=q0,(q2,1)=q3(q3,0)=q1,(q3,1)=q2q0F={q0,q3}转移表表示的DFA正规语言及其描述q1q2q3q0DFA如何接受输入符号串正规语言及其描述q2q3q0q1DFA如何接受输入符号串正规语言及其描述q2q0q1q3DFA如何接受输入符号串正规语言及其描述q2q3q0q1DFA如何接受输入符
7、号串正规语言及其描述q1q2q3q0DFA如何接受输入符号串正规语言及其描述q1q3q0q2DFA如何接受输入符号串正规语言及其描述q1q0q2q3DFA如何接受输入符号串正规语言及其描述q1q2q3q0DFA如何接受输入符号串正规语言及其描述q1q3q0q2DFA如何接受输入符号串正规语言及其描述q1q2q3q0DFA如何接受输入符号串正规语言及其描述q1q2q3q0DFA如何接受输入符号串正规语言及其描述q2q3q0q1DFA如何接受输入符号串正规语言及其描述q2q0q1q3DFA如何接受输入符号串正规
8、语言及其描述q1q3q0q2DFA如何接受输入符号串正规语言及其描述q1q2q3q0DFA如何接受输入符号串正规语言及其描述q2q3q0q1DFA如何接受输入符号串正规语言及其描述设一个DFAA=(Q,,,q0,F):QQ扩充定义:Q*Q对任何qQ，定义：1(q,)=q2若w=xa,其中x*,a,则(q,w)=((q,x),a)扩展转移
