📄 lianxiti3.4.htm

📁 建立《编译原理网络课程》的目的不仅使学生掌握构造编译程序的原理和技术

💻 HTM

字号:

<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)&nbsp;令Letter表示除这五个元音外的其它字母。<br>
					&nbsp;&nbsp;&nbsp;((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)&nbsp;A<sup>*</sup>B<sup>*</sup>....Z<sup>*</sup><br><br>
				(3)&nbsp;(0|10<sup>*</sup>1)<sup>*</sup><br><br>
				(4)&nbsp;(0|10<sup>*</sup>1)<sup>*</sup>1<br><br>
				(5)&nbsp;[分析]<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>
				&nbsp;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 + Shift + D

显示快捷键 ?

增大字号 Ctrl + =

减小字号 Ctrl + -