[理工] [離散]-文法

[gn00618777 (123)]

中正94數學  離散最後一題
                                                      m  m+n  n
Find a phrase-structure grammar to generate the set {0  1    0  |m,n>=0}

Note that a phrase-structure grammar G={V,T,S,P} consists of a vocabulary

V , a set of T consisting of terminal elements, a start symbols S from V

and a set production P .


解答是這樣 V={S,A,B,0,1}

           T={0,1}

           P={S-->AB , A-->0A1,A-->λ,B-->0B1,B-->λ}


   很納悶，這個產生規則的集合，不是要符合正規文法嗎？

   A,B應該是non-Terminal

   怎麼可以S--->AB  ，正規文法不是都是1個terminal或者1個terminal+non-terminal

                      例如：  S0---->a  | aA  嗎？
                              他怎麼可以兩個都是non-terminal (S-->AB)?

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.138.106.129
→ gn00618777:還是說產生的文法不一定要type3?
※ 編輯: gn00618777      來自: 220.138.106.129      (03/24 18:31)
→ gn00618777:像解答這個文法符合type1和type2?
推 gensim:phrase-structure grammar是type1的語言文法
→ gensim:每種語言都有其文法規則
→ gn00618777:那考試不就要看要寫哪一種文法囉？不能自己愛選哪一個
→ gn00618777:就選哪個？
→ gn00618777:還是說這個只能用type1寫的出來，正規寫不出來？
→ gn00618777:@@@?
推 gensim:在這個語言中你是沒辦法用type3的文法來表示的