形式語言與邏輯/上下文無關語言

定義（上下文無關文法）:

一個上下文無關文法是喬姆斯基文法$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}\}$.