上下文无关语言

2019-05-20 本文已影响0人 WILL_HUNTING

上下文无关文法能够描述某些具有递归结构的特征。

上下文无关文法的应用：

研究人类语言。在名词、动词、介词以及他们的短语之间的关系中存在自然的递归。
程序设计语言的规范说明和编译。

3.1 上下文无关文法

例子, $G_1$ :

$A \rightarrow 0A1$

$A \rightarrow B$

$B \rightarrow \sharp$

一个文法由一组替换规则产生，替换规则又叫做产生式。

格式：符号箭头字符串

符号：变元

字符串：变元+终结符组成

起始变元：通常第一条规则的左边

3.1.1 上下文无关文法的形式定义

定义3.1 上下文无关文法是一个4元组 $(V, \Sigma, R, S)$ , 这里

1）v是一个有穷集合，称作变元集。

$\Sigma$ 是一个与V不相交的有穷集合，称作终结符集。
R是一个有穷的规则集，每一条规则是一个变元和一个有变元和终结符组成的字符串。
$S \in V$ 是起始变元。

3.1.2上下文无关文法举例

考虑文法 $G_3=(\{S\}, \{a, b\}, R, S\})$ ，其中规则集R为：

$S \rightarrow aSb|SS|\epsilon$

如果把a看作左括弧"("、b看作右括弧")"，可以看出 $L(G_3)$ 是所有正常嵌套的括弧字符串构成的语言。

考虑文法 $G_4=(V, \Sigma, R, <EXPR>)$ ，其中 $V=\{<EXPR>, <TERM>, <FACTOR>\}$ ， $\Sigma=\{a, +, \times , (, )\}$ ，规则为：

$<EXPR> \rightarrow <EXPR> + <TERM> | <TERM>$

$<TERM> \rightarrow <TERM> \times <FACTOR> | <FACTOR>$

$<FACTOR> \rightarrow (<EXPR>) | a$$

3.1.3 设计上下文无关文法

1 许多CFG是由几个比较简单的CFG合并成的。分成几部分，并且分别构造每一部分的文法。

部分： $S_1, S_2, \dots, S_k$

加入新规则： $S \rightarrow S_1|S_2|\dots |S_k$

2 如果这个语言碰巧是正则的，可以先构造它的DFA，然后在构造它的CFG。转化方法：

对于DFA的每一个状态 $q_i$ ，设一个变元 $R_i$ ，如果 $\delta(q_i, a**=q_j$ 是DFA中的一个转移函数，则把规则 $R_i \rightarrow a R_j$ 加入CFG；

如果 $q_i$ 是DFA的接受状态，则把规则 $R_i \rightarrow \epsilon$ 加入CFG；

设 $q_0$ 是DFA的起始状态，则取 $R_0$ 作为CFG的起始变元。

3.1.4 歧义性

最左派生

当已知一个歧义文法，有时能找到一个产生相同语言的非歧义文法，但某些上下文无关语言只能用歧义文法产生，这样的语言称为固有歧义的。

3.1.5 乔姆斯基范式

定义3.5 一个上下文无关文法为乔姆斯基范式，如果他的每一个规则具有如下形式：

$A \rightarrow BC$

$A \rightarrow a$

定理3.6 任何一个上下文无关语言都能用乔姆斯基范式的上下文无关文法产生。

3.2 下推自动机

3.2.1 下推自动机的形式定义

定义3.8 下推自动机是一个6元组 $(Q, \Sigma, \Gamma, \delta, q_0, F)$ ，这里 $Q, \Sigma, \Gamma$ 和F都是有穷集合，并且

Q是状态集。
$\Sigma$ 是输入字母表。
$\Gamma$ 是栈字母表。
$\delta : Q \times \Sigma_{\epsilon} \times \Gamma_{\epsilon} \rightarrow \rho$ (Q \times \Gamma_{\epsilon})$是转移函数。
$q_0 \in Q$ 是起始状态。
$F \subseteq Q$ 是接受状态集。

下推自动机在能力上与上下文无关文法等价.

$\{0^n1^n|n \geq0\}$

非形式地描述这个语言的PDA如何工作：

读输入中的符号。每读一个0把0输入栈。一旦看见1之后，就每读一个1就把一个0弹出栈。如果栈中0被排空的时候恰好读完输入串，则接受这个输入。如果还有1没有读的时候栈变成空的；或者栈中还有0的时候1已经读完了；或者0出现在1的后面，则拒绝这个输入。

3.2.2 下推自动机机举例

$\{0_n 1_n|n \geqslant\}$

$\{a^ib^jc^k|i,j,k \geqslant 0, 且i=j或i=k\}$

$\{\omega \omega^\Re |\omega \in \{0, 1\}^\star\}$

3.2.3 与上下文无语言的等价性

定理3.12* 一个语言是上下文无关的，当且仅当存在一台下推自动机识别他。

正向：证明主要关注PDA的非确定性

反向：数学归纳法

3.3 非上下文无关语言

关于上下文无关语言的泵引理*

定理3.19 如果A是上下文无关语言，则存在数p（泵长度），使得A中任何一个长度不小于p的字符串s能够分成5段，s=uvxyz，满足下述条件

对于每一个i， $uv^ixy^iz \in A$
$|vy| > 0$
$|vxy| \leqslant p$

上一篇下一篇

猜你喜欢

热点阅读