作者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