Re: 計概的文法問題

[svanavs (svanavs)]

※ 引述《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
: 答案是Ⅱ、Ⅳ，請問該如何解呢？

 I.     S → aScB
          → aAcd
          → acAcd
          → acccd

 II.    S → aScB (S→aScB , B→d)
          → aaScBcd (S→b , B→d)
          → aabcdcd

 III.   S → aScB
          → aAcd
          → accd

 IV.    S → aScB (S→A , B→A)
          → aAcA (A→c)
          → accc

--

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 220.133.199.28
推 ysbh:thanks