编译原理实验五：有穷自动机的确定化

实验五 有穷自动机的确定化实验五 有穷自动机的确定化 一 要求一 要求 1 输入 非确定有限 穷 状态自动机 2 输出 确定化的有限 穷 状态自动 二 实验目的二 实验目的 1 熟练掌握 DFA 及 NFA 的定义及有关概念 2 理解并掌握确定的有穷自动机的化简等算法 三 实验原理三 实验原理 1 由定义可见 不确定有限自动机 NFA 与确定有限自动机 DFA 的主要区别是 1 NFA 的初始状态 S 为一个状态集 即允许有多个初始状态 2 NFA 中允许状态在某输出边上有相同的符号 即对同一个输入符号可以有 多个后继状态 即 DFA 中的 F 是单值函数 而 NFA 中的 F 是多值函数 2 NFA 确定化为 DFA 同一个字符串 可以由多条通路产生 而在实际应用中 作为描述控制过程的 自动机 通常都是确定有限自动机 DFA 因此这就需要将不确定有限自动机转 换成等价的确定有限自动机 这个过程称为不确定有限自动机的确定化 即 NFA 确定化为 DFA 下面介绍一种 NFA 的确定化算法 这种算法称为子集法 1 若 NFA 的全部初态为 S1 S2 Sn 则令 DFA 的初态为 S S1 S2 Sn 其中方括号用来表示若干个状态构成的某一状态 2 设 DFA 的状态集 K 中有一状态为 Si Si 1 Sj 若对某符号 a 在 NFA 中有 F Si Si 1 Sj a Si Si 1 Sk 则令 F Si Si 1 Sj a Si Si 1 Sk 为 DFA 的一个转换函 数 若 Si Si 1 Sk 不在 K 中 则将其作为新的状态加入到 K 中 3 重复第 2 步 直到 K 中不再有新的状态加入为止 4 上面得到的所有状态构成 DFA 的状态集 K 转换函数构成 DFA 的 F DFA 的字母表仍然是 NFA 的字母表 5 DFA 中凡是含有 NFA 终态的状态都是 DFA 的终态 3 NFA 确定化的实质是以原有状态集上的子集作为 DFA 上的一个状态 将原状 态间的转换为该子集间的转换 从而把不确定有限自动机确定化 经过确定化 后 状态数可能增加 而且可能出现一些等价状态 这时就需要简化 2 四 数据结构与算法四 数据结构与算法 struct edge string first 边的初始结点 string condition 边上的条件 string last 边的终点 string closure string a edge b 求状态集合 I 的 define max 100 int n NFA 的边数 vector value struct edge string first 边的初始结点 string condition 边上的条件 string last 边的终点 string closure string a edge b 求状态集合 I 的 for i 0 i a length i for j 0 j n j if b j first 0 a i return a string move string collection char ch edge b 状态集合 I 的 a 弧转换 int i j string s for i 0 i collection length i for j 0 j n j 5 if b j first 0 collection i return s string sort string t 字符串排序 int k i j char tt for i 0 i t length 1 i k i for j i 1 j t length j if t j t k k j tt t k t k t i t i tt return t void main int i j x 0 h length m d 0 string Condition 边上的条件 string First Last 初态 终态 string T max ss edge b new edge max cout 编译原理实验五 有穷自动机的确定化 endl cout 请输入各边信息 起点 条件 空用 for i 0 i b i first if b i first break else cin b i condition b i last n i cout 请输入 NFA 的初态及终态 First Last 6 cout 请输入 NFA 状态中的输入符号即边上的条件 Condition T x closure First b 字符串数组存储空闭包并排序 T x sort T x value push back 0 i 0 while value i 0 for j 0 j Condition length j ss ss move T i Condition j b length value size for h 0 h length h if T h sort closure ss b break if h length T x sort closure ss b value push back 0 i edge DFA new edge max for i 0 i x i 构造 DFA 的各边 for j 0 j Condition length j DFA d first T i DFA d condition Condition j ss ss sort closure move T i Condition j b b for m 0 m x m if ss T m DFA d last T m cout NFA 构造的 DFA 的各边信息如下 endl 起点 条件 终点 endl for i 0 i d i for m 0 m x m 7 if DFA i first T m cout m DFA i condition for m 0 m x m if DFA i last T m cout m endl cout 确定后的 DFA 的初态为 for m 0 m x m for j 0 j T m length j ss T m