2010-02-22

FSM的問題

(i)What is the set generated by the following phrase-structure grammar? G=(V,T,S,P), V={0,1,S}, T={0,1}, P={S->01,S->0S1}

這題答案是:

{0^n1^n n>=1}


(ii)Construct a phrase-structure grammar to generate the set {1^n0 n>=0}

這題答案是:

G=(V,T,S,P), V={0,1,S}, T={0,1}, P={S->1,S->0,S->S0}

是這樣嗎?
如果有錯 請助教能多多教我一下

2 則留言:

pai 提到...

1.我覺得是對的
2.你的答案應該錯了,你的答案可以造出
100....(S如果一直用S0替換)
題目要的是111....0或是0
我覺得應該是這樣P={S->1S,S->0}

putr 提到...

2.我寫完也覺得怪怪的
看完樓上感覺你才是對的
多謝指教 ^^