lianxiti3.4.htm
来自「建立《编译原理网络课程》的目的不仅使学生掌握构造编译程序的原理和技术」· HTM 代码 · 共 57 行
HTM
57 行
<html>
<head>
<title>编译原理</title>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<link type="text/css" rel="stylesheet" href="../css/specification.css">
</head>
<BODY>
<br>
<center><font class="title2"><b>练习3.4</b></font></center><br>
<table>
<tr>
<td class="content">
<b>答案</b><br>
(1) 令Letter表示除这五个元音外的其它字母。<br>
((letter)<sup>*</sup>A(letter)<sup>*</sup>E(letter)<sup>*</sup>I(letter)<sup>*</sup>O(letter)<sup>*</sup>U(letter))<sup>*</sup><br><br>
(2) A<sup>*</sup>B<sup>*</sup>....Z<sup>*</sup><br><br>
(3) (0|10<sup>*</sup>1)<sup>*</sup><br><br>
(4) (0|10<sup>*</sup>1)<sup>*</sup>1<br><br>
(5) [分析]<br>
设S是符合要求的串，|S|=2k+1 (k≥0）。<br>
则 S→S<sub>1</sub>0|S<sub>2</sub>1，|S<sub>1</sub>|=2k (k>0），|S<sub>2</sub>|=2k (k≥0）。<br>
且S<sub>1</sub>是{0,1}上的串，含有奇数个0和奇数个1。<br>
S<sub>2</sub>是{0,1}上的串，含有偶数个0和偶数个1。<br>
考虑有一个自动机M<sub>1</sub>接受S<sub>1</sub>，那么自动机M<sub>1</sub>如下：<br><br>
<center><img src="img/xiti3.4b.gif"></center>
和L(M<sub>1</sub>)等价的正规表达式，即S<sub>1</sub>为：<br>
((00|11)|(01|10)(00|11)<sup>*</sup>(01|10))<sup>*</sup>(01|10)(00|11)<sup>*</sup><br>
类似的考虑有一个自动机M<sub>2</sub>接受S<sub>2</sub>，那么自动机M<sub>2</sub>如下：<br><br>
<center><img src="img/xiti3.4c.gif"></center>
和L(M<sub>2</sub>)等价的正规表达式，即S<sub>2</sub>为：<br>
((00|11)|(01|10)(00|11)<sup>*</sup>(01|10))<sup>*</sup><br>
因此，S为：<br>
((00|11)|(01|10)(00|11)<sup>*</sup>(01|10))<sup>*</sup>(01|10)(00|11)<sup>*</sup>0|<br>
((00|11)|(01|10)(00|11)<sup>*</sup>(01|10))<sup>*</sup>1<br>
<br>
(6)1<sup>*</sup>|1<sup>*</sup>0(0|10)<sup>*</sup>(1|ε)<br><br>
(7)接受w的自动机如下：<br>
<center><img src="img/xiti3.4a.gif"></center>
对应的正规表达式：(1(01<sup>*</sup>0)1|0)<sup>*</sup>
</td>
</tr>
</table>
<br>
</BODY>
</html>
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?