形式言語
[math] \newcommand{\mathsetextension}[1]{% \left\{ #1 \right\}% } \newcommand{\mathsetintension}[2]{% \left\{ #1 \left| #2 \right.\right\}% } \newcommand{\mathof}[2]{% \mathop{#1}\left(#2\right)% } \newcommand{\mathderiv}{\mathrel{\mathop{\Rightarrow}}^{*}} \newcommand{\mathgen}{\rightsquigarrow} \newcommand{\mathgenfun}[1]{\mathbf{#1}} \newcommand{\mirrorim}[1]{\overleftarrow{#1}} \newcommand{\emptyword}{\varepsilon} \newcommand{\kleenecl}[1]{{#1}^{*}} \newcommand{\interpret}[1]{[\![#1]\!]} \newcommand{\mathautomaton}[1]{\mathcal{#1}} \newcommand{\mathnat}{\mathbb{N}} \newcommand{\qed}{\blacksquare} [/math]
形式言語（formal language）とは有限な記号列の集合である。
形式言語の導入
この節においては、形式言語の定義を行う。
定義 (記号列)
記号集合（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_{n}b_{1}\dots b_{m}$ である。
$w_{1}$ と $w_{2}$ が記号列を表すとき、$w_{1}$ と $w_{2}$ の連接を $w_{1}\cdot w_{2}$ または単に $w_{1}w_{2}$ で表す。
同じ記号列 $w$ を $n$ 個並べた記号列を $w^{n}$ と表す。形式的には記号列 $w$ と自然数 $n$ に対して、
- $w^{0}=\emptyword$
- $w^{n+1}=ww^{n}$
と帰納的に定義する。
同様にして記号列の集合 $L_{1}$, $L_{2}$ についてその連接を \[L_{1}L_{2}= \mathsetintension{wv}{w\in L_{1}, v\in L_{2}} \] と定義する。
また，記号列の集合 $L$ に対して、$L^{n}$ （$n$ は自然数）を
- $L^{0}=\mathsetextension{\emptyword}$
- $L^{n+1}=\mathsetintension{wv}{w\in L, v\in L^{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$ を固定する。
連接
連接について述べる。
定義 (連接)
上記の連接の節を参照。
例 (連接)
- 記号列mathと記号列pediaの連接はmathpediaである。
- 記号列noと記号列whereの連接はnowhereである。
- 記号列counterと記号列exampleの連接はcounterexampleである。
- 記号列ultraと記号列sevenの連接はultrasevenである。
- 記号列bicycleと記号列repairmanの連接はbicyclerepairmanである。
- 記号列 $\emptyword$ と記号列 $\emptyword$ の連接は $\emptyword$ である。
命題 (連接の性質)
- 任意の記号列 $w$ に対して、$w\emptyword=\emptyword w=w$ である。
連接とモノイド
- 連接 $\cdot$ を $\kleenecl{\Sigma}$ 上の演算とみなすことで、$(\kleenecl{\Sigma}, \cdot)$
はモノイドになる。単位元は $\emptyword$ である。
- 特に $(\kleenecl{\Sigma}, \cdot)$ を $\Sigma$ が生成する自由モノイドという。
Kleene閉包
Kleene閉包（Kleene closure） について述べる。
定義 (Kleene閉包)
上記のKleene閉包の節を参照。
例 (Kleene閉包)
命題 (Kleene閉包の性質)
- 任意の記号列の集合 $L$ に対して、$\kleenecl{\kleenecl{L}}=\kleenecl{L}$ である。
接頭語と接尾語
形式言語の接頭語と接尾語について述べる。
定義 (接頭語、接尾語)
$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}$ を次のように帰納的に定義する。
- $w=\emptyword$ のとき、$\mirrorim{w}=\emptyword$ である。
- $w=av$ のとき、$\mirrorim{w}=\mirrorim{v}a$ である。
例 (鏡像)
- 記号列mathpediaの鏡像はaidephtamである。
- 記号列tomatoの鏡像はotamotである。
- 記号列dogの鏡像はgodである。
- 記号列topの鏡像はpotである。
- 記号列lolの鏡像はlolである。
命題 (鏡像の性質)
- $\mirrorim{\mirrorim{w}}=w$
商
形式言語の商について述べる。
定義 1 (商)
$\Sigma$ 上の形式言語 $L$、文字列 $w \in \kleenecl{\Sigma}$ に対して $L$ の $w$ による左商（left quotient）を \[w^{-1}L:= \mathsetintension{v \in \kleenecl{\Sigma}}{wv \in L} \] と定める。
また、$L$ の $w$ による右商（right quotient）を \[Lw^{-1}:=\mathsetintension{v \in \kleenecl{\Sigma}}{vw \in L} \] と定める。
形式言語 $L$ の左商全体の集合を ${\kleenecl{\Sigma}}^{-1}L$ 右商全体の集合を $L{\Sigma^{*}}^{-1}$ で表す。つまり、 \begin{align*}% {\kleenecl{\Sigma}}^{-1}L &:= \mathsetintension{w^{-1}L}{w \in \kleenecl{\Sigma}} \\ L{\kleenecl{\Sigma}}^{-1} &:= \mathsetintension{Lw^{-1}}{w \in \kleenecl{\Sigma}} \end{align*} である。
（言語の）数え上げ関数と母関数
形式言語の数え上げ関数と母関数について述べる。
定義 (数え上げ関数)
形式言語 $L$ の数え上げ関数（counting function） $\Gamma_{L}:{\mathnat\to\mathnat}$ とは \[\Gamma_{L}(n)=\mathof{\#}{\mathsetintension{w\in L}{|w|=n}}\] で定義される関数である（ただし、$\#$ は有限集合を受け取りそこに所属する元の個数を返す関数）。
定義 (母関数)
形式言語 $L$ の母関数（generating function）とは形式的べき級数 \[\mathof{\mathgenfun{L}}{z}:=\sum_{n\geq 0} \mathof{\Gamma_{L}}{n}z^{n}\] のことである（ただし、$\Gamma_{L}$ は $L$ の数え上げ関数）。
参考文献
- 新屋 良磨、オートマトン理論再考、コンピュータ ソフトウェア、2017、34 巻、3 号、p. 3_3-3_35、公開日 2017/09/25、Print ISSN 0289-6540、https://doi.org/10.11309/jssst.34.3_3、https://www.jstage.jst.go.jp/article/jssst/34/3/34_3_3/_article/-char/ja
- 五十嵐喜英他、『数理情報科学シリーズ ２４ オートマトンと形式言語の基礎』、牧野書店、2011
