CFG表示无上下文语法。它是一种形式语法，用于以给定形式语言生成所有可能的字符串模式。上下文无关的语法G可以由四个元组定义为：
G = (V, T, P, S)其中，
G是语法，由一组生产规则组成。它用于生成语言的字符串。
T是终端符号的最终集合。用小写字母表示。
V是非终结符的最终集合。用大写字母表示。
P是一组生产规则，用于将字符串中的非终结符（在生产的左侧）替换为其他终端或非终结符（在生产的右侧）。
S是用于导出字符串的起始符号。我们可以通过在生产的右侧重复替换一个非终结符来导出字符串，直到所有非终结符都被终结符替换为止。
范例1：
为集合∑ = {a}上具有任意多个a的语言构造CFG。
解：
我们知道上述语言的正则表达式是
r.e. = a*正则表达式的生产规则如下：
S → aSrule 1
S → εrule 2现在，如果要派生字符串“ aaaaaa”，我们可以从开始符号开始。
S
aS
aaSrule 1
aaaSrule 1
aaaaSrule 1
aaaaaSrule 1
aaaaaaSrule 1
aaaaaaεrule 2
aaaaaa那里。 = a *可以生成一组字符串{ε，a，aa，aaa，… ..}。我们可以有一个空字符串，因为S是开始符号，规则2给出S→ε。
范例2：
为正则表达式（0 1）*构造CFG *
解：
CFG可以由下式给出：
Production rule (P):
S → 0S | 1S
S → ε规则是0和1与开始符号的组合。由于（0 1）*表示{ε，0，1，01，10，00，11，… .}。在这个集合中，ε是一个字符串，因此在规则中，我们可以设置规则S→ε。
范例3：
为语言L = {wcwR |其中w€（a，b）*}。
解：
【自动机上下文无关语法（CFG）】可以为给定语言生成的字符串是{aacaa，bcb，abcba，bacab，abbcbba，… .}
语法可能是：
S → aSarule 1
S → bSbrule 2
S → crule 3现在，如果要派生字符串“ abbcbba”，我们可以从开始符号开始。
S → aSa
S → abSbafrom rule 2
S → abbSbbafrom rule 2
S → abbcbbafrom rule 3因此，可以从给定的生产规则派生任何此类字符串。
范例4：
为语言L = anb2n构建CFG，其中n> = 1。
解：
可以为给定语言生成的字符串是{abb，aabbbb，aaabbbbbb … .}。
语法可能是：
S → aSbb | abb现在，如果要派生字符串“ aabbbb”，我们可以从开始符号开始。
S → aSbb
S → aabbbb推荐阅读
- 从Moore机到Mealy机的转换
- Arden定理
- RE到FA的自动机转换
- 自动机正则表达式的例子
- 自动机正则表达式
- 从NFA到DFA的自动机转换
- 自动机从ε NFA到DFA的转换
- 消除ε转换的自动机
- 非确定性有限自动机的例子