题目
2.7 已知正规式((a |b)||aa)b和正规式(a |b)×b。-|||-(1)试用有限自动机的等价性证明这两个正规式是等价的;-|||-(2)给出相应的正规文法。
题目解答
答案
解析
步骤 1：正规式((a |b)||aa)b对应的NFA
根据正规式((a |b)||aa)b，可以构造对应的NFA。NFA的状态转换图如下：
- 初始状态为X，接受状态为Y。
- X通过ε转换到1，1通过a或b转换到2，2通过a转换到3，3通过b转换到Y。
- X通过ε转换到4，4通过a转换到5，5通过a转换到6，6通过b转换到Y。
步骤 2：正规式((a |b)||aa)b对应的DFA
将上述NFA确定化为DFA，得到的状态转换矩阵如下：
- 状态1：输入a或b都转换到状态2。
- 状态2：输入a转换到状态3，输入b转换到状态2。
- 状态3：输入a或b都转换到状态2。
- 状态2和状态3都是接受状态。
步骤 3：正规式(a|b)^bb对应的NFA
根据正规式(a|b)^bb，可以构造对应的NFA。NFA的状态转换图如下：
- 初始状态为X，接受状态为Y。
- X通过ε转换到1，1通过a或b转换到2，2通过b转换到Y。
步骤 4：正规式(a|b)^bb对应的DFA
将上述NFA确定化为DFA，得到的状态转换矩阵如下：
- 状态1：输入a或b都转换到状态2。
- 状态2：输入a或b都转换到状态2。
- 状态2是接受状态。
步骤 5：比较两个DFA
比较两个DFA的状态转换矩阵，发现它们是完全一样的，因此两个正规式是等价的。
步骤 6：给出相应的正规文法
根据DFA的状态转换矩阵，可以构造相应的正规文法。令A对应状态1，B对应状态2，则相应的正规文法G[A]为：
- A → aA | bB | b
- B → aB | bB | b
由于B的产生式与A的产生式相同，可以合并为一个产生式，得到最简正规文法G[S]为：
- S → aS | bS | b
根据正规式((a |b)||aa)b，可以构造对应的NFA。NFA的状态转换图如下：
- 初始状态为X，接受状态为Y。
- X通过ε转换到1，1通过a或b转换到2，2通过a转换到3，3通过b转换到Y。
- X通过ε转换到4，4通过a转换到5，5通过a转换到6，6通过b转换到Y。
步骤 2：正规式((a |b)||aa)b对应的DFA
将上述NFA确定化为DFA，得到的状态转换矩阵如下：
- 状态1：输入a或b都转换到状态2。
- 状态2：输入a转换到状态3，输入b转换到状态2。
- 状态3：输入a或b都转换到状态2。
- 状态2和状态3都是接受状态。
步骤 3：正规式(a|b)^bb对应的NFA
根据正规式(a|b)^bb，可以构造对应的NFA。NFA的状态转换图如下：
- 初始状态为X，接受状态为Y。
- X通过ε转换到1，1通过a或b转换到2，2通过b转换到Y。
步骤 4：正规式(a|b)^bb对应的DFA
将上述NFA确定化为DFA，得到的状态转换矩阵如下：
- 状态1：输入a或b都转换到状态2。
- 状态2：输入a或b都转换到状态2。
- 状态2是接受状态。
步骤 5：比较两个DFA
比较两个DFA的状态转换矩阵，发现它们是完全一样的，因此两个正规式是等价的。
步骤 6：给出相应的正规文法
根据DFA的状态转换矩阵，可以构造相应的正规文法。令A对应状态1，B对应状态2，则相应的正规文法G[A]为：
- A → aA | bB | b
- B → aB | bB | b
由于B的产生式与A的产生式相同，可以合并为一个产生式，得到最简正规文法G[S]为：
- S → aS | bS | b