grammar - 这是什么语言的意思？

Question

这是语言：

L = { w belong {a,b,c}* | |w|= 3 * number(a) (w) }

那么，这是什么意思呢？

Answer 1

这意味着 L 是w由符号'a'、'b'' 和组成的字符串语言'c'，其中字符串的长度w 等于字符串中'a'存在的符号数量的 3 倍w。

这个语法的产生式应该是这样的，如果它加一，'a'那么它也加二'b'，或二'c'，或一'b'；一 'c'。检查以下语法：

S → ^ | SaSMSM |  SMSaSM | SMSMSa   
M → b | c

这里的^意思是ε。

生成aabbcc使用最右推导

1. S → SaSMSM
2. 使用 S → ^
   S → SaSMSM → aSMSM将 rhs 中的第一个 S 替换为 ^
3. 替换 S → SaSMSM
   S → SaSMSM → aSaSMSMMSM
4. 使用 S → ^
   S → SaSMSM → aSaSMSMMSM → aaSMSMMSM
5. 使用 S → ^
   S → SaSMSM → aSaSMSMMSM → aaSMSMMSM → aaMSMMSM
6. M → b
   S → SaSMSM → aSaSMSMMSM → aaSMSMMSM → aaMSMMSM → aabSMMSM
7. 使用 S → ^
   S → SaSMSM → aSaSMSMMSM → aaSMSMMSM → aaMSMMSM → aabSMMSM → aabMMSM
8. M → b
   S → SaSMSM → aSaSMSMMSM → aaSMSMMSM → aaMSMMSM → aabSMMSM → aabMMSM → aabbMSM
9. M → c
   S → SaSMSM → aSaSMSMMSM → aaSMSMMSM → aaMSMMSM → aabSMMSM → aabMMSM → aabbMSM → aabbcSM
10. 使用 S → ^
    S → SaSMSM → aSaSMSMMSM → aaSMSMMSM → aaMSMMSM → aabSMMSM → aabMMSM → aabbMSM → aabbcSM → aabbcM
11. M → c
    S → SaSMSM → aSaSMSMMSM → aaSMSMMSM → aaMSMMSM → aabSMMSM → aabMMSM → aabbMSM → aabbcSM → aabbcM → aabbcc