編譯原理 第二章習(xí)題答案

1、第2章習(xí)題解答1.文法G[S]為：SAc|aBAabBbc寫出L(G[S])的全部元素。[答案]S=Ac=abc或S=aB=abc所以L(G[S])=abc==============================================2.文法G[N]為：ND|NDD0|1|2|3|4|5|6|7|8|9G[N]的語言是什么？[答案]G[N]的語言是V。V=0123456789N=ND=NDD....=NDDDD...D=D

2、......D===============================================3.已知文法G[S]：S→dABA→aA|aB→ε|bB問：相應(yīng)的正規(guī)式是什么？G[S]能否改寫成為等價的正規(guī)文法？[答案]正規(guī)式是daab；凡是諸如此類的題都應(yīng)按此思路進行，本題可做為一個基本代表?；舅悸肥沁@樣的：要求符合anbncm，因為a與b要求個數(shù)相等，所以把它們應(yīng)看作一個整體單元進行，而cm做為另一個單位，初步產(chǎn)生式就

3、應(yīng)寫為SAB，其中A推出anbn，B推出cm。因為m可為0，故上式進一步改寫為SAB|A。接下來考慮A凡是要求兩個終結(jié)符個數(shù)相等的問題，都應(yīng)寫為AaAb|ab形式，對于B就很容易寫成BBc|c了。==============================================================================6.寫一文法，使其語言是偶正整數(shù)集合。要求：(1)允許0開頭；(2)不允許0開頭。[答案