Re: 計概的文法問題

[SONGya168 (伃)]

※ 引述《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)
→ ysbh:thanks