括弧列の判定

記号の集合を $\Sigma = \{\,\texttt{(}\,,\,\texttt{)}\,,\,\texttt{[}\,,\,\texttt{]}\,\}$ とし、対応の取れた括弧列の集合 $B \subseteq \Sigma^{*}$ を、次の 3 つの規則で生成される最小の集合として定める。

入力 $w \in \Sigma^{*}$ に対する次のアルゴリズム $\mathcal{A}$ を考える。空のスタック $S$ から始め、$w$ を左から 1 文字ずつ読む。

• 読んだ文字が開き括弧なら、それを $S$ に $\mathrm{push}$ する。
• 読んだ文字が閉じ括弧なら、$S$ が空であれば直ちに拒否し、そうでなければ $\mathrm{top}$ を見て $\mathrm{pop}$ し、取り出した文字がその閉じ括弧と同種の開き括弧でなければ拒否する。

全文字を読み終えた時点で $S$ が空なら受理、空でなければ拒否する。このとき、$\mathcal{A}$ が $w$ を受理することと $w \in B$ であることは同値である。また $\mathcal{A}$ の実行時間は $O(|w|)$ であり、$w$ を受理する場合は $\Theta(|w|)$ である（途中で拒否すれば早く終わる）。