例:文法G[S] S→aAS→aA→aAA→dAA→aA→→d 先有: s=aAa A=(aAldA) l (ald) 再将A的正规式变换为A=(ad)A(ad 据表中规则2变换为:A=(ad)y(ad) 再将A右端代入S的正规式得:S=a(ad)y(ald)|a 再利用正规式的代数变换可依次得到 S=a((ad)*(ad)a s=a (ad) 即a(ad)*为所求
例:文法 G［S］ S→aA S→a A→aA A→dA A→a A→d 先有： S=aA|a A=（aA|dA）|(a|d） 再将A的正规式变换为A=(a|d)A|(a|d) 据表中规则2变换为：A=(a|d)*(a|d) 再将A右端代入S的正规式得： S=a((a|d )*(a|d))|a 再利用正规式的代数变换可依次得到 S=a((a|d)* (a|d ) |ε) S＝a（a|d）* 即 a（a|d）*为所求
3.22有限自动机 形式语言的识别在编译理论中起着重要的作用。语言识别器 个程序,它以串x作为输入,x是语言的句子是回答“是” 否则回答“不是”。有限自动机(也称有穷自动机)它也是 种识别程序,它能准确地识别正现集,即识别正规文法所定义 的语言和正规式所表示的集合,引人有穷自动机这个理论,正 是为了词法分析程序的自动构造寻找的特殊方法和工具 有限自动机分为两类;确定的有限自动机( Deterministic Finite automata)和不确定的有限自动机( Nondeterministic Finite automata),虽然确定有限自动机和非确定有限自动机 面都能识别正规集,前者任一状态对于某输入符号只存在一种 状态的转换,后者有些状态对于某输入符号可能存在多种状态 的转换。前者执行效率高,占存储空间大,后者反之。下面我 们给出确定的有穷自动机和不确定的有穷自动机的定义,有关 概念及不确定的有穷自动机的确定化算法
3.2.2有限自动机 形式语言的识别在编译理论中起着重要的作用。语言识别器 是一个程序，它以串x作为输入，x是语言的句子是回答“是”， 否则回答“不是”。有限自动机（也称有穷自动机）它也是一 种识别程序，它能准确地识别正现集，即识别正规文法所定义 的语言和正规式所表示的集合，引人有穷自动机这个理论，正 是为了词法分析程序的自动构造寻找的特殊方法和工具。 有限自动机分为两类；确定的有限自动机（Deterministic Finite Automata）和不确定的有限自动机（Nondeterministic Finite Automata），虽然确定有限自动机和非确定有限自动机 面都能识别正规集，前者任一状态对于某输入符号只存在一种 状态的转换，后者有些状态对于某输入符号可能存在多种状态 的转换。前者执行效率高，占存储空间大，后者反之。下面我 们给出确定的有穷自动机和不确定的有穷自动机的定义，有关 概念及不确定的有穷自动机的确定化算法
1.确定的有限自动机(DFA) 定义32 一个确定的有限自动机(DFA)M是一个五元组:M=(K,E,f, S,Z)其中 (1)K是一个有穷集,它的每个元素称为一个状态 (2)Σ是一个有穷字母表,它的每个元素称为一个输入字符 (3)f是一个从K×Σ→K的单值映象 4)S∈K,是唯一的初始状态(开始状态) (5)zsK,是非空的终止状态集,终止状态也称接受状态或结 束状态
1.确定的有限自动机（DFA） 定义 3.2 一个确定的有限自动机（DFA）M是一个五元组：M=(K,Σ，f， S，Z）其中 (1) K是一个有穷集，它的每个元素称为一个状态 (2) Σ是一个有穷字母表，它的每个元素称为一个输入字符 (3) f是一个从K×Σ→K的单值映象 (4) S∈K，是唯一的初始状态（开始状态） (5) Z K，是非空的终止状态集，终止状态也称接受状态或结 束状态
f(Sa)=S'意味着,当现行状态为S,输入字符为a是时,将转换 到下一个状态S’。这里把S称为S的一个后继状态。 个DFA可以也可以表示成一个状态图(或称状态转换图 简称转换图)。假定DFAM含有m个状态,n个输入字符,那 么这个状态图含有m个结点,每个结点最多有n个弧射出,整个 图含有唯一的一个初态结点和若干个终态结点,初态结点以 “=>”,终态结点用双圈表示。若f(S,a)=S则从状态结点S到 状态结点S画标记为a的弧;
f(S,a)=S’意味着，当现行状态为S，输入字符为a是时，将转换 到下一个状态S’ 。这里把S’ 称为S的一个后继状态。 一个 DFA可以也可以表示成一个状态图（或称状态转换图 简称转换图）。假定DFA M含有m个状态，n个输入字符，那 么这个状态图含有m个结点，每个结点最多有n个弧射出，整个 图含有唯—的一个初态结点和若干个终态结点，初态结点以 “=>”，终态结点用双圈表示。若f(S，a)=S’则从状态结点S到 状态结点S’画标记为a的弧；