作者SONGya168 (伃)
看板Grad-ProbAsk
標題Re: 計概的文法問題
時間Mon Jun 8 21:01:36 2009
※ 引述《ysbh (烏龜回娘家)》之銘言：
: 142.設有一文法如下，其中大寫字母表示non-terminals，而小寫字母則表示terminals︰
: S → a S c B | A | b
: A → c A | c
: B → d | A
: 以下四個句子 (sentences)，何者可由上述文法所產生？
: I. acccbd II. aabcdcd III. acd IV. accc
: 答案是Ⅱ、Ⅳ，請問該如何解呢？
由於四個選項皆a開頭,因此 是以S開始表示
步驟順序: ! @ # $ % ^ & *
I. acccbd
S
/ | \
!a S
%c B A b
/
@| \ / \
a S c B A b
^d A
/ \
#c A c
/
\
c A
$c
僅可表示出 acccd 及IV. accc
II. aabcdcd
S
/ | \
!a S
^c B A b
/ | \
/ \
@a S
$c B A b
&d A
/ |
\ / \
a S c B A
#b %d A
可表示出 aabcdcd
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.216.12.77
※ 編輯: SONGya168 來自: 61.216.12.77 (06/08 21:08)
1F：→ ysbh:thanks 06/10 17:58