形式语言和自动机总结DFA、NFA正则语言

news/2024/4/20 1:26:38/文章来源:https://blog.csdn.net/qq_62260432/article/details/130142341

第一章DFA

形式定义和状态转移函数:

DFA是一种特殊的NFA，

A={Q, $\sum$ , $\delta$ , $q_0$ ,F} Q:输入状态集，∑:字母表，δ:状态转移函数Q×∑→Q q0∈Q初始状态 F终结集

设计举例

1.设计接受偶数个0和偶数个1串的DFA

2.设计 DFA 接受 {0,1} 上的字符串 w, 且 w 是 3 的倍数的二进制表示(前面可以有0)

3.要求同上,前面不允许有0

扔出来一个死状态。

4.Design a DFA for L = {w ∈ {0,1} ∗ | w contains both 00 and 11 as substrings}.(最后一个状态没加入01)

第2章NFA

NFA的设计

NFA的习题很少可以尝试将DFA的题变成NFA的题。

1.设计一个由01构成的串，1是偶数0是奇数的NFA

对0 1的状态进行区分

2. Design an NFA within four states for the language { 0 }* $\cup$ { 01 }*.

3.Design an NFA for L = { w∈{0,1}∗ | w contains an equal number of occurrences of the substrings 01 and 10 }

4.由 0 和 1 构成的串中, 接受全部以 01 结尾的串

5.. 设计 L = {w ∈ {0,1} $^{+}$ w的首尾字符相同}的 NFA 很容易忘了中间的情况

6.L = {w ∈ {0,1} *|w either begins or ends (or both) with 01. }

7.对以下几种语言设计NFA :

8.Design a NFA for L = {w ∈ {0,1} ∗ | w contains both 00 and 11 as substrings}.

9.Design an NFA for L = {w ∈ {0,1} ∗ | w contains an equal number of occurrences of the substrings 01 and 10}.

做这种题的时候观察他的结构,猜想这种结构有什么特点.永远不要忘了中间的情况。

ε-NFA:

空转移有利于减少我们的状态并且自然的将条件分隔开来。

DFA和NFA的相互转换

等价性证明

NFA->DFA 理解思想吧。

NFA转DFA 子集构造法:

注意一点:对于 $\varnothing$ 与其他子集一样用到就保留，没用到就去掉，NFA卡死，对应到DFA就是死状态

2.L = {(0+1)*|倒数第三个字符是1}的NFA转换成DFA

ε-NFA转换为DFA

第3-4章正则表达式

正则表达式的设计举例

正则表达式的运算

正则表达式的优先级

举例

1.倒数第三个字符是1

（0+1)*1(0+1)(0+1)

2.不含有连续的0

（1+01）*（0+ $\varepsilon$ ）

3.含有000

（0+1）*000（0+1）*

4.不含000/111的正则语言（/代表两个式等价的)

(1+01+001)*( $\varepsilon$ +0+00) / 1*(0 $1^{+}$ +00 $1^{+}$ )

DFA $\Leftrightarrow$ 正则表达式

为什么要引入:有的时候我们做设计正则表达式习题的时候发现直接想很困难，我们不如利用正则表达式和DFA之间的等价性，构造出DFA，进而构造正则表达式。

1.设计不含001/110的正则表达式

2.设计不含010/101的正则表达式

方法1：直接猜测法:

$0^{*}(1+000^{*})0^{*}$

方法2:DFA转正则表达式

3.设计不含001/110的正则语言

4 . L = { w∈{0,1}* | w contains both 01 and 10 as substrings }

这个题的出错点在于可能忘记考虑010 101的情况

分类相加的方法:

$(0+1)^{*}01(0+1)^{*}10(0+1)^{*}+(0+1)^{*}10(0+1)^{*}01(0+1)^{*}+(0+1)^{*}010(0+1)^{*}+(0+1)^{*}101(0+1)^{*}$

直接的方法：合并情况的方法

$(0+1)^{*}(100^{*}1+011^{*}1)(0+1)^{*}$

5.The set of all strings with an equal number of 0's and 1's, such that no prefix has two more 0's than 1's, nor two more 1's than 0's.

$(01+10)^{*}$

6. Let L={ w | w∈{0,1}* and if there are two 0s of w, they must be separated by 1 or 11 }

$1^{*}(0+\varepsilon )(110+10)^{*}1^{*} or 1*(01+011)^{*}(0+\varepsilon)^{*}$

|11 | 11 |

explaination : $1^{*}0$ | 10 | 10 |................................

正则语言的性质

泵引理老师上课也讲了不少，感觉上课再看看书上的例题熟悉一下思路基本就没问题了，后面PDA那里也有一个泵引理，不过考试还是喜欢正则语言的泵引理。我自己的感觉是取语言中的一个串，如果不符合那么这个语言就不是正则语言。

1.证明泵引理

往多泵
往少泵
利用语言的封闭性证明:if $L_{1} L_{2}$ 都是正则语言L = $L_{1}\cup /\cap /\setminus L_{2}$ ，或者其反转 $L^{R}$ 也是正则语言，如果不是正则语言那么L不一定不是正则语言。

具体实例见第四章习题，一般的方法是取语言中的子串。利用语言中的一个元素不是正则来确定不是正则语言。

1.证明回文字符不是正则语言：

2.Prove that L = { $a^{i}b^{j}c^{k}$ |i + j = k |is not regular with pumping lemma.}

5. 取0的N次方 1的N次方

6.The set of strings of 0’s and 1’s whose length is a perfect square.

取 $0^{m}1^{n} \,\,m+n=N^{2}$ 利用放缩

7.The set of strings of 0’s and 1’s that are of the form ww, that is some string repeated.

$0^{N}1^{N}0^{N}1^{N}$ 证明不是正则语言。

2.利用封闭性的泵引理证明:

1.The set of strings of the form $0^{i}1^{j}$ such that the greatest common divisor of i and j is 1.

设L={ $0^{i}1^{j}$ |gcd(i,j)=1} L'= $\overline{L}$ $\cap$ 0*1*={ $0^{i}1^{j}$ |gcd(i,j)>1}

如果L是正则语言那么L的反转也是正则语言，取 $0^{N}1^{N}$ (N不是素数)由泵引理， $0^{N-m}1^{N}$ 不和题意

2.DFA的最小化：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.luyixian.cn/news_show_286215.aspx

如若内容造成侵权/违法违规/事实不符，请联系dt猫网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！