描述a、ab、abc、ac的语言的上下文无关语法

Question

我正试图弄清楚对于这样描述的语言来说，什么是CFG：

• 只有一个a
• 0或更多b
• 0或更多c

我试过这个：S -> a | Sb | Sc

或者类似的东西：

S -> a | B | C

B -> Bb

C -> Cc

但它似乎不起作用。有没有其他/更好的方法用CFG来描述这种语言？

Answer 1

对于只有一个A而没有其他内容的字符串语言，语法只是

S -> a

您的语言不同之处在于，还允许零个或多个b和c。它们可以在单曲a之前或之后出现，也可以按任何顺序出现。该语言的语法"；任何顺序中的任何数量的b和c都是

T -> bT | cT | e

因为我们可以在单个a的任一侧有任意数量的b和c，这表明我们可以将非终端T的乘积添加到s的乘积中，并更改s的乘积以导出任一侧有T的a：

S -> TaT
T -> bT | cT | e

这语法应该行得通。证明这个语法是正确的只是一个练习。

还有其他可行的方法。一种可行的方法是为这种正则语言制作DFA，然后将其重写为语法。如果以直接的方式完成，语法将是无上下文的。

q0 -> bq0
q0 -> cq0
q0 -> aq1
q1 -> bq1
q1 -> cq1
q1 -> e