形式语言与逻辑/上下文无关语言

定义（上下文无关文法）:

一个上下文无关文法是乔姆斯基文法$G=(\Sigma ,N,P,S)$，其所有产生式都具有以下形式

$V\to \alpha$,

其中$V\in N$ 和 $\alpha \in (N\cup \Sigma )(N\cup \Sigma )^{*}$.

定义（上下文无关语言）:

一个上下文无关语言是字母表$\Sigma$上的语言 $L$，使得存在一个上下文无关的乔姆斯基文法$G$，它精确地接受$L$.

定义（Dyck 语言）:

设$n\in \mathbb {N}$。阶为 $n$ 的Dyck 语言$D_{n}$ 是形式语言

$D_{n}:=\{w=a_{1}a_{2}\cdots a_{k}\in \Sigma ^{*}|k\in \mathbb {N} \wedge \forall (m,j)\in \{1,\ldots ,n\}\times \{1,\ldots ,k\}:|\{l\leq j|a_{l}=)_{m}\}|\leq |\{l\leq j|a_{l}=(_{m}\}|\wedge |\{l\leq n|a_{l}=)_{m}\}|=|\{l\leq n|a_{l}=)_{m}\}|\}$

其字母表是 $\Sigma =\{(_{1},\ldots ,(_{n},)_{1},\ldots ,)_{n}\}$.