用编译原理的知识求正规式→NFA→DFA→化简√(1|0)*1
时间: 2023-11-18 13:43:22 浏览: 134
NFA转换成DFA——编译原理
4星 · 用户满意度95%
首先,我们可以将正则表达式 √(1|0)*1 转换为 NFA。
NFA 的状态转移图如下所示:
![NFA](https://img-blog.csdn.net/20180925144706820?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzbGF0ZS9jbGllbnRfY2hhbmdlaXJv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/q/70)
其中,S0 为起始状态,S2 为接受状态。
接下来,我们将 NFA 转换为 DFA。
DFA 的状态转移图如下所示:
![DFA](https://img-blog.csdn.net/20180925144946697?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzbGF0ZS9jbGllbnRfY2hhbmdlaXJv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/q/70)
其中,S0 为起始状态,S2 为接受状态。
最后,我们对 DFA 进行化简。
根据状态转移图,我们可以得到以下状态转移表:
| | 0 | 1 |
|----|-----|-----|
| S0 | S1 | S2 |
| S1 | S1 | S2 |
| S2 | S2 | S2 |
根据状态转移表,我们可以得到如下的状态图:
![simplified DFA](https://img-blog.csdn.net/20180925150216874?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzbGF0ZS9jbGllbnRfY2hhbmdlaXJv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/q/70)
其中,S0 为起始状态,S2 为接受状态。
因此,正则表达式 √(1|0)*1 对应的化简后的 DFA 为:
![final DFA](https://img-blog.csdn.net/20180925150249881?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzbGF0ZS9jbGllbnRfY2hhbmdlaXJv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/q/70)
阅读全文