a b {0}0* {0,1} {1} {0,1}* {0,1} {1} {1} {0}
转换为 a b 0* 1 2 1* 1 2 2 0
{2，3} {0，1}
{2，3}a={0,3} {2},{3},{0,1}
{0,1}a={1,1} {0,1}b={2,2} （2）解：首先把M的状态分为两组：终态组{0}，和非终态组{1，2，3，4,5} {1,2,3,4,5}a={1,3,0,5} {1,2,3,4,5}b={4,3,2,5}
由于{4}a={0} {1,2,3,5}a={1,3,5}
因此应将{1,2,3,4,5}划分为{4},{1,2,3,5} G=({0}{4}{1,2,3,5}) {1,2,3,5}a={1,3,5} {1,2,3,5}b={4,3,2}
因为{1,5}b={4} {23}b={2,3}
所以应将{1,2,3,5}划分为{1,5}{2,3} G=({0}{1,5}{2,3}{4})
{1,5}a={1,5} {1,5}b={4} 所以{1,5} 不用再划分 {2,3}a={1,3} {2,3}b={3,2}
因为 {2}a={1} {3}a={3} 所以{2,3}应划分为{2}{3} 所以化简后为G＝（ {0},{2},{3},{4},{1,5}）
7.去除多余产生式后，构造NFA如下
aADabbbSZbbbbBQaa
此时G=( {0},{1,2,3,4,5} ) 6
确定化，构造DFA矩阵 a b S A Q A A B,Z B,Z Q D Q Q D,Z D A B D,Z A D B Q D 变换为 a b 00 1 3 1 1 2 2* 3 4 3 3 5 4 1 6 5* 1 4 6 3 4 化简： G={(0,1,3,4,6),(2,5)} {0,1,3,4,6}a={1,3}
{0,1,3,4,6}b={2,3,4,5,6}
所以将{0,1,3,4,6}划分为 {0,4,6}{1,3} G={(0,4,6),(1,3),(2,5)}
{0,4,6}b={3,6,4} 所以 划分为{0},{4,6} G={(0),(4,6),(1,3),(2,5)}
不能再划分，分别用 0，4，1，2代表各状态，构造DFA状态转换图如下；
a0a,b1a4bbab2
8．代入得
S = 0(1S|1)| 1(0S|0) = 01(S|ε) | 10(S|ε) = (01|10)(S|ε)
= (01|10)S | (01|10)
7
= (01|10)*
(01|10)
构造NFA
0A11SZ01B0
由NFA可得正规式为(01|10)*
(01|10)=(01|10)+
9.状态转换函数不是全函数,增加死状态8, G={(1,2,3,4,5,8),(6,7)}
(1,2,3,4,5,8)a=(3,4,8) (3,4)应分出 (1,2,3,4,5,8)b=(2,6,7,8) (1,2,3,4,5,8)c=(3,8) (1,2,3,4,5,8)d=(3,8)
所以应将(1,2,3,4,5,8)分为(1,2,5,8), (3,4) G={(1,2,5,8),(3,4),(6,7)}
(1,2,5,8)a=(3,4,8) 8应分出 (1,2,5,8)b=(2,8) (1,2,5,8)c=(8) (1,2,5,8)d=(8)
G={(1,2,5),(8),(3,4),(6,7)} (1,2,5)a=(3,4,8) 5应分出
G={(1,2), (3,4),5, (6,7) ,(8) } 去掉死状态8,
最终结果为 (1,2) (3,4) 5,(6,7) 以1,3,5,6代替,最简DFA为bc1a3b6bda5
正规式:b*a(da|c)*bb*
第五章
1.
8
S->a | ^ |( T ) T -> T , S | S (a,(a,a))
S => ( T ) => ( T , S ) => ( S , S ) => ( a , S) => ( a, ( T )) =>(a , ( T , S ) ) => (a , ( S , S )) => (a , ( a , a ) ) S=>(T) => (T,S) => (S,S) => ( ( T ) , S ) => ( ( T , S ) , S ) => ( ( T , S , S ) , S ) => ( ( S , S , S ) , S ) => ( ( ( T ) , S , S ) , S ) => ( ( ( T , S ) , S , S ) , S ) =>( ( ( S , S ) , S , S ) , S ) => ( ( ( a , S ) , S , S ) , S ) => ( ( ( a , a ) , S , S ) , S ) => ( ( ( a , a ) , ^ , S ) , S ) => ( ( ( a , a ) , ^ , ( T ) ) , S )
=> ( ( ( a , a ) , ^ , ( S ) ) , S ) => ( ( ( a , a ) , ^ , ( a ) ) , S ) => ( ( ( a , a ) , ^ , ( a ) ) , a )
S->a | ^ |( T ) T -> T , S T -> S
消除直接左递归： S->a | ^ |( T ) T -> S T’
T’ -> , S T’ | ξ
SELECT ( S->a) = {a} SELECT ( S->^) = {^}
SELECT ( S->( T ) ) = { ( }
SELECT ( T -> S T’) = { a , ^ , ( } SELECT ( T’ -> , S T’ ) = { , }
SELECT ( T’ ->ξ) = FOLLOW ( T’ ) = FOLLOW ( T ) = { ） }
构造预测分析表 S T T’
a -> a -> S T’ ^ -> ^ -> S T’ ( -> ( T ) -> S T’ ) ->ξ , -> , S T’ # 分析符号串 （ a , a ）#
分析栈 剩余输入串 所用产生式 #S ( a , a) # S -> ( T ) # ) T ( ( a , a) # ( 匹配 # ) T a , a ) # T -> S T’ # ) T’ S a , a ) # S -> a # ) T’ a a , a ) # a 匹配 # ) T’ ，a) # T’ -> , S T’ # ) T’ S , , a ) # , 匹配 # ) T’ S a ) # S->a # ) T’ a a ) # a匹配 # ) T’ ) # T’ ->ξ # ) ) # )匹配 # # 接受
9
2.
E->TE’ E’->+E E’->ξ T->FT’ T’->T T’->ξ F->PF’ F’->*F’ F’->ξ P->(E) P->a P->b P->∧ 非终结符名 E E’ T T’ F F’ P 是否＝>ε 否 是 否 是 否 是 否 FIRST集 {（，a，b，^} {+,ε} {（，a，b，^} {ε, （，a，b，^} {（，a，b，^} {*,ε} {（，a，b，^} FOLLOW集 {#，）} {#，）} {＋，#，）} {＋，#，）} {（，a，b，^，＋，#，）} {（，a，b，^，＋，#，）} {*，（，a，b，^，#，）} SELECT（E－>TE’）=FIRST(TE’)=FIRST(T)= {（，a，b，^）
SELECT（E’－>+E）={+}
SELECT（E’－>ε）=FOLLOW(E’)= {#，)}
SELECT（T－>FT’）=FIRST（F）= {（，a，b，^} SELECT（T’ —>T）=FIRST（T）= {（，a，b，^） SELECT(T’－>ε)=FOLLOW(T’)= {＋，#，)} SELECT(F －>PF’)=FIRST(F)= {（，a，b，^} SELECT(F’－>*F’)={*}
SELECT(F’－>ε)=FOLLOW(F’)= {（，a，b，^，＋，#，）}
3. S->MH S->a H->Lso H->ξ K->dML K->ξ L->eHf M->K M->bLM FIRST ( S ) =FIRST(MH)= FIRST ( M ) ∪ FIRST ( H ) ∪ {ξ} ∪ {a}= {a, d , b , e ,ξ} FIRST( H ) = FIRST ( L ) ∪ {ξ}= { e , ξ} FIRST( K ) = { d , ξ}
FIRST( M ) = FIRST ( K ) ∪ { b } = { d , b ,ξ}
FOLLOW ( S ) = { # , o }
FOLLOW ( H ) = FOLLOW ( S ) ∪ { f } = { f , # , o } FOLLOW ( K ) = FOLLOW ( M ) = { e , # , o }
FOLLOW ( L ) ={ FIRST ( S ) –{ξ} } ∪{o} ∪ FOLLOW ( K ) ∪ { FIRST ( M ) –{ξ} } ∪ FOLLOW ( M ) = {a, d , b , e , # , o }
FOLLOW ( M ) ={ FIRST ( H ) –{ξ} } ∪ FOLLOW ( S )
∪{ FIRST ( L ) –{ξ} } = { e , # , o }
SELECT ( S-> M H) = ( FIRST ( M H) –{ξ} ) ∪ FOLLOW ( S )
= ( FIRST( M ) ∪ FIRST ( H ) –{ξ} ) ∪ FOLLOW ( S ) = { d , b , e , # , o } SELECT ( S-> a ) = { a }
SELECT ( H->L S o ) = FIRST(L S o) = { e }
10