数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究设计一个识别至少包含两个 0 和至少包含两个 1 的字符串的 DFA
确定性有限自动机 (DFA) 是一个 5 元组
M=(Q, Σ, δ,q0,F)
其中，
- Q：称为状态的有限集合。
- Σ：称为字母表的有限集合。
- δ：Q × Σ → Q 是转移函数。
- q0 ϵ Q 是起始状态或初始状态。
- F：终止状态或接受状态。
问题
构造一个识别至少包含两个 0 和至少包含两个 1 的字符串的 DFA。
解决方案
基于给定条件在字母表 Σ ={0,1} 上生成的语言是 -
L={0011,001011,0001010,0011001,010101,……}
给定的语言接受至少两个 0，意味着它可以接受两个或两个以上的 0，并且至少两个 1，意味着它接受两个或两个以上的 1。
假设，
- 输入 - 00010
- 输出 - 字符串被拒绝
因为，给定的输入不包含至少两个 1。
即使它至少包含两个 0，它也不会接受该字符串。
为了接受字符串，两个条件都必须满足，如果其中一个不满足，则该字符串将不会被机器接受。
- 输入 - 001001001
- 输出 - 字符串被接受
现在为给定的输入构造 DFA -
| 状态 | 0 的数量 | 1 的数量 |
|---|---|---|
| → q0 | 0 | 0 |
| q1 | 0 | 1 |
| q2 | 0 | > =2 |
| q3 | 1 | 0 |
| q4 | 1 | 1 |
| q5 | 1 | > =2 |
| q6 | > =2 | 0 |
| q7 | > =2 | 1 |
| *q8 | > =2 | > =2 |
DFA 将如下所示 -
解释
如果输入是 1，则 1 的数量增加到 1。转移到状态 q1。如果输入是 0，则 0 的数量增加到 1。转移到状态 q3。
如果输入是 1，则 1 的数量增加到 2。转移到状态 q2。如果输入是 0，则 0 的数量增加到 1。转移到状态 q4。
如果输入是 1，则 1 的数量始终增加 1。然后保持在同一状态。如果输入是 0，则 0 的数量增加到 1。转移到状态 q5。
如果输入是 1，则 1 的数量增加到 1。转移到状态 q4。如果输入是 0，则 0 的数量增加到 2。转移到状态 q6。
如果输入是 1，则 1 的数量增加到 2。转移到状态 q5。如果输入是 0，则 0 的数量增加到 2。转移到状态 q7。
如果输入是 1，则 1 的数量始终增加 1。然后保持在同一状态。如果输入是 0，则 0 的数量增加到 2。转移到状态 q8
如果输入是 1，则 1 的数量增加到 1。转移到状态 q7。如果输入是 0，则 0 的数量持续增加 1。然后保持在同一状态。
如果输入是 1，则 1 的数量增加到 2。转移到状态 q8。如果输入是 0，则 0 的数量持续增加 1。然后保持在同一状态。
如果输入是 1，则 1 的数量始终增加 1。然后保持在同一状态。如果输入是 0，则 0 的数量持续增加 1。然后保持在同一状态。
最后，如果字符串结束，则它被接受。
3K+ 浏览量
