标签：0A1 文法 right 变元 理论 计算 left rightarrow

第2章 上下文无关文法

2.1 概述

一个文法有一组替换规则组成，替换规则又称为产生式。如下G:

\[A \rightarrow 0A1 \]

\[A \rightarrow B \]

\[A \rightarrow \# \]

也可写为

\[A\rightarrow 0A1|B| \# \]

第一条规则的左边的变元称为起始变元

（符号称为变元如A，B。终止符如01#即小写字母、数字或特殊符号表示）

如用文法G生成000#111字符串。获取字符串的替换序列称为派生，即：

\[A\rightarrow 0A1\rightarrow 00A00\rightarrow 000A000 \rightarrow 000\#111 \]

也可用语法分析树描述这一派生过程

上述方式生成的所有字符串称为该文法的语言，用\(L(G_1)表示\)，可知该文法\(L(G) = \left\{0^n\# 1^n | n\ge 0 \right\}\), 称为上下文无关语言(CFL)
\(———————————————————————————————\)

\[G_2 = (\left\{S \right\}, \left\{a, b \right\}, R, S) \]

其中规则集R：

\[S\rightarrow aSb|\ SS| \varepsilon \]

S是起始变元
上述方式就是上下文无关文法(CFA)的形式化定义

由CFL构造CFG

标签：0A1,文法,right,变元,理论,计算,left,rightarrow
From： https://www.cnblogs.com/a2leaf/p/17758154.html