数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚
法律研究构造以“a”开始但无子串“aab”的 DFA
问题
给定构造确定有限自动机 (DFA) 的语言是，字母表 ∑={a,b}，字符串以“a”开头但不包含子串“aab”。
解决方案
如果输入为：“baabba”
输出为：字符串不被接受
因为该字符串没有以“a”开头，并且生成了子串“abb”，
DFA 转移图
以“a”开头但子串不为“aab”的字符串的 DFA 转移图为 −
转移表
转移表如下 −
| 状态 | 输入 (a) | 输入 (b) |
|---|---|---|
| → 0 | 1* | 4（死状态） |
| 1* | 2* | 3* |
| 2* | 2* | 4（死状态） |
| 3* | 1* | 3* |
| 4（死状态） | 4（死状态） | 4（死状态） |
更新于: 15-Jun-2021
978 次浏览
广告