📄 4.10.1.htm
字号:
<html>
<head>
<title>4.1的解答</title>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<link type="text/css" rel="stylesheet" href="../css/specification.css">
</head>
<body background="../images/background2.gif">
<center>
<center><font class="title2"><b>练习4.1</b></font></center><br>
</center>
<table><tr><td> </td>
<td class="content">
解：<br>
(1) 不含运算的正规式a和b显然能被此文法生成。设含运算个数为n(n<k)的正规表达式r<sub>1</sub>和r<sub>2</sub>能被文法生成，即R<img src="images/equalplus.gif" width="20" height="19">r<sub>1</sub>，R<img src="images/equalplus.gif" width="20" height="19">r<sub>2</sub> <br>
那么，对于含k个运算的正规表达式r，r必有下列形式之一：<br>
① r = r<sub>1</sub> | r<sub>2</sub><br>
② r = r<sub>1</sub>r<sub>2</sub><br>
③ r = r<sub>1</sub><sup>*</sup> <br>
④ r＝(r<sub>1</sub>)
<br>
对于r = r<sub>1</sub> | r<sub>2 </sub>,使用文法规则推导如下:
<table align=center width=450 class="content">
<tr><td>R</td><td>=> R' | 'R</td></tr>
<tr><td></td><td><img src="images/equalplus.gif" width="20" height="19"> r<sub>1</sub> | R</td></tr>
<tr><td></td><td><img src="images/equalplus.gif" width="20" height="19"> r<sub>1</sub> |
r<sub>2</sub></td></tr>
</table>
∴ R <img src="images/equalplus.gif" width="20" height="19"> r<sub>1 </sub> |
r<sub>2</sub> <br>
可类似构造R <img src="images/equalplus.gif" width="20" height="19"> r<sub>1</sub>r<sub>2</sub>，R <img src="images/equalplus.gif" width="20" height="19">
r<sub>1</sub><sup>*</sup>， R <img src="images/equalplus.gif" width="20" height="19">
(r<sub>1</sub>)<br>
证毕。<br><br>
(2) 对于句子ab*可构造两个最左推导:<br>
R => RR => aR => aR* => ab* <br>
R => R* => RR* => aR* => ab* <br><br>
(3) 改写G[R]的产生式如下:<br>
R → R' | 'T | T <br>
T → TF | F <br>
F → F* | C <br>
C → (R) | a | b <br>
</td></tr></table>
</body>
</html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -