アルファベット・語彙・復号

空でない有限集合 $\Sigma$ をアルファベット、その元を記号という。記号の有限列を記号列といい、その全体を $\Sigma^{*}$、長さ 1 以上のものの全体を $\Sigma^{+}$ と書く。記号列 $s, t$ をつないだ列を $st$ と書き（連結）、長さを $|s|$ と書く。空列を $\varepsilon$ と書く。

有限集合 $V$ と写像 $\langle\!\langle \cdot \rangle\!\rangle : V \to \Sigma^{+}$ の組を語彙といい、$V$ の元をトークン id（または単にトークン）、$\langle\!\langle t \rangle\!\rangle$ をトークン $t$ の表す記号列という。$V$ の元の有限列 $x = (t_1, \ldots, t_n) \in V^{*}$ をトークン列といい、

を $x$ の復号という（$n = 0$ のときは $\mathrm{dec}(\varepsilon) = \varepsilon$）。$V_0 := \Sigma$、$\langle\!\langle a \rangle\!\rangle := a$ で定まる語彙を基本語彙という。