制作上下文无关文法和平衡括号

Question

我需要为带平衡括号的字母表 {a,),(} 构建上下文无关文法。

我不确定平衡括号的确切含义以及我如何为它构建上下文无关语法。如果有人能写下这方面的步骤，我将不胜感激。

Answer 1

为了给出一个粗略的递归解释，括号的平衡通常意味着任何单词，如果限制在括号内，要么

1. 以左括号开始，以右括号结束；
2. 是这些词的串联；
3. 是通过在前面加上右括号从这些词中得到的。

这个想法可以形式化为上下文无关文法，如下所示。

starting symbol: E
terminal symbols: a,(,)
E => a
E => Ea
E => (E)
E => EE

根据this的解释，这里的context free是指产生式规则的left-hand边不包含终结符，只有一个non-terminal 符号.