上下文无关语言

上下文无关语言 (Context-Free Languages)

定义 (Definition): 上下文无关语言是由上下文无关文法（CFG）生成的语言。CFG 是一种形式语法，其产生式的形式为 $A\to \alpha$，其中 $A$ 是单个非终结符号，$\alpha$ 是终结符号和非终结符号的序列。

Context-free languages are languages generated by context-free grammars (CFGs). A CFG is a type of formal grammar where the production rules have the form $A\to \alpha$, where $A$ is a single non-terminal symbol, and $\alpha$ is a sequence of terminal and non-terminal symbols.

例子 (Example)

假设有一个上下文无关文法 $G=(\{S\},\{a,b\},\{S\to aSb\mid ϵ\},S)$。这个文法生成的语言是 $\{ϵ,ab,aabb,aaabbb,\dots \}$。

Consider a context-free grammar $G=(\{S\},\{a,b\},\{S\to aSb\mid ϵ\},S)$. The language generated by this grammar is $\{ϵ,ab,aabb,aaabbb,\dots \}$.

上下文无关语言的封闭性 (Closure Properties of Context-Free Languages)

上下文无关语言在某些运算下是封闭的，包括并、连接和 Kleene 闭包，但不包括交和差。

Context-free languages are closed under certain operations, including union, concatenation, and Kleene closure, but not intersection and difference.

封闭性运算 (Closure Operations):

• 并 (Union): 如果 $L_1$ 和 $L_2$ 是上下文无关语言，则 $L_1\cup L_2$ 也是上下文无关语言。

  If $L_1$ and $L_2$ are context-free languages, then $L_1\cup L_2$ is also a context-free language.

• 连接 (Concatenation): 如果 $L_1$ 和 $L_2$ 是上下文无关语言，则 $L_1{L}_2$ 也是上下文无关语言。

  If $L_1$ and $L_2$ are context-free languages, then $L_1{L}_2$ is also a context-free language.

• Kleene 闭包 (Kleene Closure): 如果 $L$ 是上下文无关语言，则 $L^{\ast }$ 也是上下文无关语言。

  If $L$ is a context-free language, then $L^{\ast }$ is also a context-free language.