正规式、dfa nfa.ppt

1 构造与正规式（a|b|c）*a等价的DFA: 答：（1）与此正规式对应的NFA为,（2）状态转换矩阵为：,状态空间重新命名，得到的状态转换矩阵为:,(3)所以此等价的DFA为：开始状态为0 ，终态集为{1} ，状态集是为{0,1,2} ，输入字母表是{a,b,c}状态转换矩阵如上构造正规式 (0|1)*00 相应的DFA并进行化简 答：（1）与此正规式对应的NFA为,,,（3）最小化： {1，2，3} {4}{1，2，3}0={2，4} {1,3} {2} {4},,（2）状态转换矩阵为：,(4)所以此等价的DFA为：开始状态为1 ，终态集为{3} ，状态集为{1,2,3} ，输入字母表是{0,1} 状态转换图如上3 请写出该字母表{0，1}中，接受以0开头，以1结尾的字符串集合的正规表达式？并构造与之等价的DFA构造等价的最小化的DFA 答:(一)相应的正规式为0（0|1）*1(二) ①与此正规式对应的NFA为,②状态转换矩阵为：,③状态空间重新命名，得到的状态转换矩阵为:,,,④将其最小化，首先得到两个子集{1，2，3}和{4} 由于状态2和3在输入0都到达状态3，输入1都到达状态4，所以{2}和{3}等价。

所以子集为{1}，{2，3}，{4}⑤所以最小DFA的初态为1，终态集为{3}，状态集为 {1，2，3}，字母表为{a,b},状态转换矩阵如上4 写出在字母表{a,b}上，不是a开头，但以aa结尾的字符串集合的正规表达式？并构造与之等价的DFA构造等价的最小化的DFA 答:(一)相应的正规式为b（a|b）*aa (二) ①与此正规式对应的NFA为,②状态转换矩阵为：,③状态空间重新命名，得到的状态转换矩阵为:,,,④将其最小化，首先划分状态{1，2，3，4}，{5}两个 状态由于状态2和状态4输入a后都达到状态3，输入b 后都达到4，所以状态2和状态4等价⑤所以最小DFA的初态集是0，终态集为{4}， 状态集为{1，2，3，4}，字母表为{a,b} ， 状态转换矩阵如上5 构造一个DFA，它接受={a，b}上所有包含ab的字符串 答:(一)相应的正规式为(a|b)*ab(a|b)*(二) ①与此正规式对应的NFA为,,,,,a a  a b  b b,②状态转换矩阵为：,,,③ 最小化： {0，1，2} {3，4，5} {0， 2}，1， {3，4，5},,,④所以此等价的DFA为：开始状态为0 ，终态集为{3} ，状态集为{0,1,3} ，输入字母表是{a,b} 状态转换图如上。

6: 将R=a(a|b)*转换成相应的正则文法 令转换成文法G=(VN,VT,P,S) 其中VT={a,b}， 文法开始符为S 首先形成S→a(a|b)*,然后变换 S→aA A→(a|b)*,A→(a|b)A A→ε,A→aA A→bA,,,最终有产生式： S→aA ， A→ ε， A→aA，A→bA,7：将文法G[S]转换成正规式G：S→a A|aA→bA|b 先由产生式得: S=aA|a A=b*b 将A代入S中得: S=ab*b|a 利用正规式变换得 S=a(b*b|ε)=ab*说明:d*d|ε =(ε|b|bb|…)b|ε=b|bb|…|ε= b* 所求正规式为ab*,。