> 文章列表 > 形式语言和自动机总结----正则语言RE

形式语言和自动机总结----正则语言RE

文章列表

形式语言和自动机总结----正则语言RE

第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 |................................

7.设计(a+b)*的文法

$S\\rightarrow SaS|SbS|\\varepsilon$

正则语言的性质

泵引理老师上课也讲了不少，感觉上课再看看书上的例题熟悉一下思路基本就没问题了，后面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.}

3.

4.

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.

2.DFA的最小化：

NFA转正则语言

其实是一个递归算法:

正则语言转 $\\varepsilon$ -NFA

规则翻课件