构造与a(a|b)*b(a|b)等价的状态最少的DFA,按如下步骤求解
发布网友
发布时间：2022-04-25 06:31
共1个回答
热心网友
时间：2023-11-03 10:40
构造正规式1(0|1)*101相应的DFA。
先构造NFA
确定化 0 1 X A A A AB AB AC AB AC A ABY ABY AC AB
重新命名，令AB为B。
DFA最小化
首先得到两个子集K1 = {1,2,3} 和 K2 = {4}。
考察K1：由于{1,2,3}a = {1,2，4} K1，也 K2，所以K1可需要被分割。
又因为{1,3}a = {2}，{1,3}b = {3}，
所以将原状态集合分割成以下子集：K11={2}，K12={1，3}。
目前划分得到的子集为：K11={2}，K12={1，3}，K2 = {4}。
考察K12：{1,3}a = {2} K1，{1,3}b = {3}K1，所以K1不可再分割
扩展资料
词汇分析法的条件
1、输入缓冲区
成对且对半互补的输入缓冲区模式。
n: 取2的整次幂；每个半区的末尾设置标志“ eof ” 表示读入该半区的源程序的结束；
B：单词w开始指针； F：扫描w的指针；
两个缓冲区的输入模式
2、预处理程序： （作用）
1） 减少内存空间占用；
2） 减轻扫描器实质性处理的负担；
3、预处理程序主要任务：
1） 滤掉源程序中的非单词成分(如无用空格；换行符等)；
2） 其他的预处理工作:滤掉注释；宏替换；文件包含的嵌入；条件编译的嵌入。
