上下文无关文法

上下文无关语法是一种形式语法, 用于以给定形式语言生成所有可能的字符串。

上下文无关文法G可以由四个元组定义为：

G= (V, T, P, S)

哪里,

G描述语法

T描述了一组有限的终端符号。

V描述了一组有限的非终端符号

P描述了一组生产规则

S是开始符号。

在CFG中, 起始符号用于导出字符串。你可以通过在生产的右侧重复替换一个非终结符来导出字符串, 直到所有非终结符都被终结符替换为止。

例：

	L= {wcwR | w € (a, b)*}

生产规则：

S → aSa
S → bSb
S → c

现在检查abbcbba字符串是否可以从给定的CFG派生。

S ⇒ aSa
S ⇒ abSba
S ⇒ abbSbba
S ⇒ abbcbba

通过递归应用产品S→aSa, S→bSb, 最后应用产品S→c, 我们得到字符串abbcbba。