离散数学(16) 陈斌 gischen@pku.edu.cn 2009.12.25

目录 数理逻辑 集合论 图论 抽象代数 形式语言和自动机 语言和对语言的研究 形式语言的语法表示 有限状态自动机 半群、机器和语言

语法和语言的表示BNF BNF（Backus-Naur Form）范式 1960年提出，用于描述ALGOL60语言 形式简单，仅包含三个符号 “::=”，定义为；“|”，或；“<>”，用来区分非终结符 可以表示2、3型语法（上下文无关、正则） 产生式左部仅有一个非终结符 相同左部的产生式合并用“|”隔开 非终结符用“<>”标记

语法和语言的表示BNF BNF例子：“中文句子” BNF例子：“a(bb)*c” <句子>::=<主语><谓语> <主语>::=张三|李四 <谓语>::=<副词><动词> <副词>::=深情地|狂野地 <动词>::=歌唱|奔跑 BNF例子：“a(bb)*c” <v0>::=a<w> <w>::=bb<w>|c 递归出现一次，并在最右，称为正规的，3型语法中的递归产生式都是正规的

语法和语言的表示BNF BNF例子：“十进制数” <十进制数>::=<无符号整数> | <小数> | <无符号整数><小数> <无符号整数>::=<数字> | <数字><无符号整数> <小数>::=.<无符号整数> <数字>::=0|1|2|3|4|5|6|7|8|9

语法和语言的表示BNF BNF例子：“标识符” 字母开始的字母数字串，用于程序设计语言中的变量、函数等名称 <标识符>::=<字母> | <字母><后部> <后部>::=<字母> | <数字> | <字母><后部> | <数字><后部> <字母>::=a|b|c|d|e|…..|z <数字>::=0|1|2|3|4|5|6|7|8|9

语法和语言的表示BNF 扩展BNF 可选项：用“[]”表示 重复项：用“{}”表示重复0次或者多次 便于区分单个符号的终结符，加引号 <if语句>::=if <逻辑表达式> then <语句> [ else <语句> ] end if; 重复项：用“{}”表示重复0次或者多次 <标识符>::=<字母>{<字母>|<数字>} 便于区分单个符号的终结符，加引号 <语句序列>::=<语句> { “;” <语句> } 有时也用粗体字表示终结符，非终结符不加尖括号，可读性更好

语法和语言的表示BNF 用BNF定义BNF  <规则> ::= <非终结符>::=<表达式> <非终结符> ::= <<单词>> <单词> ::= <字母> | <字母><单词> <表达式> ::= <项> | <项>|<表达式> <项> ::= <因子> | <因子><项> <因子> ::= <单词> | <非终结符>

语法和语言的表示 语法图（Syntax Diagram） 用方框表示非终结符，用圆表示终结符 用带箭头线表示连接关系和连接顺序 类似程序流程图 顺序结构（连接） 可选分支结构（BNF或） 循环结构（非终结符递归） w a b <w>::=ab<w> a w w w1 w2 w3 b <w>::=a | b <w>::=<w1><w2><w3>

语法图化简与等价 <v0>::=a<w>，<w>::=bb<w>|c

语法图化简与等价 例子“标识符”

语法图化简与等价 例子“十进制数”

语法图化简与等价 例子“十进制数”

语法图化简与等价 例子“十进制数”

正则语法和正则表达式 S是有限集合，LS*。则L是正则集合，当且仅当对某个正则语法G，有L=L(G) 将G的语法组合为一个大图，其中仅包含v0和终结符，称作主导图（master diagram） 图中终结符对应正则表达式中的终结符

主导图翻译成正则表达式 串联子图，对应子表达式α1α2 并联子图，对应子表达式α1|α2 回路子图，对应子表达式α* D1 D2 D1 D

主导图翻译成正则表达式 a) a|b|c* b) (a|b)cd* c) (a|bc)*

有限状态机 给定一个字符串，判定是否属于给定语法G的语言L(G) 机器machine 一般来说，这是个难解的问题 对于正则语法和正则语言，可以通过一个“识别机器”来判定 机器machine 一个系统，接受输入，改变自身的状态，产生输出 状态指为了完成机器的任务而对输入序列进行的归类 如果状态的数目有限，称为有限状态机（Finite State Machine）

有限状态机 有限状态机FSM是一个五元组M(A,S,Y,s0,F) A:输入字符串的字母表 S:机器的有限状态集合 s0∈S:初始状态 F:S×A→S：状态转移函数，指明在某个状态下接受输入字符所引起的状态变迁

有限状态机例子 A={a,b} S={s0,s1,s2}，Y={s0,s1}，s0初始状态 F如下表 F a b s0 s1 s2

状态图 FSM通常用状态图来表示 状态图D=D(M)是带标记的有向图，节点为状态，转移函数决定边的走向和标记 接受状态用双圈表示 如果F(sj,a)=sk，则从节点si做标记为a的有向边到节点sk 初始状态s0用一个特殊的无源箭头标识

状态图例子 a,b a b s2 s1 b s0 a

有限状态机M决定的语言L M所识别的A上的所有字符串 看看上图的例子是否识别 例子机器识别什么模式的字符串？ w=a1a2…am∈A*，确定一个状态序列s0,s1,s2…sm，其中F(si-1,ai)=si 也就是确定拟路径P=(s0,a1,s1,a2,s2,…,am,sm) 如果sm∈Y则称M识别w 看看上图的例子是否识别 ababba、baab、空串 例子机器识别什么模式的字符串？ 所有不包含连续两个b的字符串

正则语言和FSM Kleen定理：字母表A上的形式语言L是正则的当且仅当存在一个有限状态机M使得L=L(M) 例：构造自动机M，识别恰好以bb结尾的字符串 正则表达式：(a|b)*bb a b b b s0 s1 s2 s2 a a

泵Pumping引理 长度超过状态数目的接受串w，都可以表示成w=xyz形式，而xynz都会被M接受 设w对应的状态序列为s0,s1,s2,…,sn n大于状态的数目|S|，所以根据鸽笼原理必有si=sj(i<j) 令x=a1a2…ai，y=ai+1…aj，z=aj+1…an x以si状态结尾，xy以sj=si状态结尾，所以xym也以状态si结尾，xymz结尾状态仍为sn y x z s0 si s2 sn

泵引理应用※ 证明：L={ambm:m>0}不是正则语言 我们以前的例子amcbm也不是正则语言 假设L是正则语言，则有有限状态机M接受L，假设M状态个数为k 令w=akbk，则一定有|w|>k，根据泵引理，w=xyz，其中y非空，而且xy2z也被M接受 如果y仅含有a或仅含有b，那么xy2z中a,b的个数就不相等了，应该不属于L 如果y同时含有a和b那么y2中一定会出现a在b之后的情况， xy2z也应该不属于L 两个矛盾说明假设错误，L不是正则语言 我们以前的例子amcbm也不是正则语言

参考文献 离散数学结构，王家钦编著，清华大学出版社 离散数学，[美]S.利普舒尔茨 M.利普森著，科学出版社

END 特殊符号表 ∴,∵,╞═╡,╞═,∈,≠,∑,↓,∪,∩,╞,┠PC αΑ,βΒ,γΓ,δΔ,εΕ,ζΖ,ηΗ,θΘ,ιΙ,κΚ,λΛ,μΜ,νΝ,ξΞ,οΟ,πΠ,ρΡ,ς΢,σΣ,τΤ,υΥ,φΦ,χΧ,ψΨ,ωΩ {¬,∧,∨,→,↔} ≦≧≠≤ø 