![[Mathpedia]](image/pukiwiki.png "[Mathpedia]")
形式言語 †形式言語（formal language）とは有限な記号列の集合である。 $\global\def\mathnat{\mathbb{N}}$ $\global\gdef\mathgenfun#1{\mathbf{#1}}$ $\global\def\emptyword{\varepsilon}$ $\global\def\kleenecl#1{{#1}^{*}}$ $\global\def\mirrorim#1{\overleftarrow{#1}}$ $\global\def\interpret#1{[\![#1]\!]}$ 形式言語の導入 †この節においては、形式言語の定義を行う。 記号列 †記号集合（alphabet）とは記号（letter）の 空でない集合である。 通常、形式言語を考える際は記号集合に有限性を課すことが多い。 本稿においても記号集合は特に断らない限り有限であるとする。 記号集合 $\Sigma$ の元を有限個並べたものを 語（word）や 有限記号列（finite string）、また 単に記号列（string）などという。 以下では記号列で統一する。 記号列 $w$ の長さ（length）とは記号列を構成する 記号の個数である。 $w$ の長さを $\left|w\right|$ とあらわす。 長さ $0$ の記号列を空列（empty string または empty word）という。 以下 $\emptyword$ によって空列を表す。 連接 †記号列 $a_1\dots a_n$ と $b_1\dots b_m$ の 連接（concatenation）とは 記号列 $a_1\dots a_nb_1\dots b_m$ である。 $w_1$ と $w_2$ が記号列を表すとき、 $w_1$ と $w_2$ の連接を $w_1\cdot w_2$ または単に $w_1w_2$ で表す。 同じ記号列 $w$ を $n$ 個並べた記号列を $w^n$ と表す。 形式的には記号列 $w$ と自然数 $n$ に対して、
と帰納的に定義する。 同様にして記号列の集合 $L_1$, $L_2$ についてその連接を $$L_1L_2=\left\{ wv \left| w\in L_1, v\in L_2 \right.\right\} $$ と定義する。 また，記号列の集合 $L$ に対して、$L^n$ （$n$ は自然数）を
と帰納的に定義する。 Kleene閉包 †記号列の集合 $L$ のKleene閉包（Kleene closure） $\kleenecl{L}$ は $$ \kleenecl{L} = \bigcup_{n=0}^{\infty} L^{n} $$ と定義される。 記号集合 $\Sigma$ のKleene閉包 $\kleenecl{\Sigma}$ は、 $\Sigma$ の元を長さ $1$ の記号列とみなすことで 自然に定義される。 形式言語の定義 †記号集合$\Sigma$上の形式言語（formal language）とは $\kleenecl{\Sigma}$の部分集合である。 特に誤解のない限り、形式言語のことを単に言語（language）と呼ぶこともある。 形式言語を扱う上でよく使われる演算など †この節においては形式言語を考える際によく使われる演算などの 定義・解説を行う。 以下では，特に断りのない限り記号集合 $\Sigma$ を固定する。 連接 †連接について述べる。 連接の定義 †上記の連接の節を参照。 連接の例 †
連接の性質 †
連接とモノイド †
接頭語と接尾語 †形式言語の接頭語と接尾語について述べる。 接頭語と接尾語の定義 †$w=a_{0}\ldots a_{n}$ を記号列とする（ただし、すべての $i$ に対して $a_{i}$ は記号であって、$a_{i}\neq \emptyword$ とする）。 $w_{p}=a_{0}\ldots a_{n_{0}}$ （ただし、$0\leq n_{0}\leq n$）であるとき、$w_{p}$ を $w$ の接頭語（prefix）と言う。 $w$ の接頭語 $w_{p}$ が $|w_{p}|<|w|$ を満たすとき、$w_{p}$ を真の接頭語（proper prefix）と言う。 $w_{s}=a_{n_{0}}\ldots a_{n}$ （ただし、$0\leq n_{0}\leq n$）であるとき、$w_{s}$ を $w$ の接尾語（suffix）と言う。 $w$ の接尾語 $w_{s}$ が $|w_{s}|<|w|$ を満たすとき、$w_{s}$ を真の接尾語（proper suffix）と言う。 鏡像 †鏡像について述べる。 鏡像の定義 †$\kleenecl{\Sigma}$ の元 $w$ の 鏡像（mirror image） $\mirrorim{w}$ を次のように帰納的に定義する。
鏡像の例 †
鏡像の性質 †
商 †形式言語の商について述べる。 商の定義 †$\Sigma$ 上の形式言語 $L$、文字列 $w \in \kleenecl{\Sigma}$ に対して $L$ の $w$ による左商（left quotient）を $$w^{-1}L := \left\{ v \in \kleenecl{\Sigma} \left| wv \in L \right. \right\}$$ と定める。 また、$L$ の $w$ による右商（right quotient）を $$Lw^{-1} := \left\{ v \in \kleenecl{\Sigma} \left| vw \in L \right. \right\}$$ と定める。 形式言語 $L$ の左商全体の集合を ${\kleenecl{\Sigma}}^{-1}L$ 右商全体の集合を $L{\Sigma^{*}}^{-1}$ で表す。つまり、 $${\kleenecl{\Sigma}}^{-1}L := \left\{ w^{-1}L | w \in \kleenecl{\Sigma} \right\}$$ $$L{\kleenecl{\Sigma}}^{-1} := \left\{ Lw^{-1} | w \in \kleenecl{\Sigma} \right\}$$ である。 （言語の）数え上げ関数と母関数 †形式言語の数え上げ関数と母関数について述べる。 数え上げ関数の定義 †形式言語 $L$ の数え上げ関数（counting function） $\Gamma_{L}:{\mathnat\to\mathnat}$ とは $$\Gamma_{L}(n)=\#\left(\left\{w\in L \left| |w|=n \right.\right\}\right)$$ で定義される関数である（ただし、$\#$ は有限集合を受け取りそこに所属する元の個数を返す関数）。 母関数の定義 †形式言語 $L$ の母関数（generating function）とは形式的べき級数 $$\mathgenfun{L}(z):=\sum_{n\geq 0} \Gamma_{L}(n)z^{n}$$ のことである（ただし、$\Gamma_{L}$ は $L$ の数え上げ関数）。 参考文献 †
関連項目 † |
