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 則留言:

  1. 匿名2010年2月22日 中午12:02

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

    回覆刪除
  2. 匿名2010年2月22日 中午12:45

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

    回覆刪除