形式言語

形式言語(formal language)とは有限な記号列の集合である。

$\global\def\mathnat{\mathbb{N}}$ $\global\gdef\mathgenfun#1{\mathbf{#1}}$

形式言語の導入

この節においては、形式言語の定義を行う。

記号列

記号集合(alphabet)とは記号(letter)の 空でない集合である。 通常、形式言語を考える際は記号集合に有限性を課すことが多い。 本稿においても記号集合は特に断らない限り有限であるとする。

記号集合 $\Sigma$ の元を有限個並べたものを 記号列(finite string)または語(word)という。

記号列 $w$ の長さ(length)とは記号列を構成する 記号の個数である。 $w$ の長さを $\left|w\right|$ とあらわす。

長さ $0$ の記号列を空列(empty string または empty word)という。以下 $\varepsilon$ によって空列を表す。

連接

記号列 $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$ に対して、

  1. $w^0 = \varepsilon$
  2. $w^{n+1} = ww^{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$ は自然数)を

  1. $L^0 =\left\{ \varepsilon \right\}$
  2. $L^{n+1} = \left\{ wv \left| w\in L, v\in L^{n} \right.\right\}$

と帰納的に定義する。

Kleene閉包

記号列の集合 $L$ のKleene閉包(Kleene closure) $L^{*}$ は $$ L^{*} = \bigcup_{n=0}^{\infty} L^{n} $$ と定義される。

記号集合 $\Sigma$ のKleene閉包 $\Sigma^{*}$ は、 $\Sigma$ の元を長さ $1$ の記号列とみなすことで 自然に定義される。

形式言語の定義

記号集合$\Sigma$上の形式言語(formal language)とは $\Sigma^{*}$の部分集合である。

特に誤解のない限り、形式言語のことを単に言語(language)と呼ぶこともある。

形式言語を扱う上でよく使われる演算など

この節においては形式言語を考える際によく使われる演算などの 定義・解説を行う。 以下では,特に断りのない限り記号集合 $\Sigma$ を固定する。

連接

連接の定義

上記の連接の節を参照。

連接の例

  • 記号列mathと記号列pediaの連接はmathpediaである。
  • 記号列noと記号列whereの連接はnowhereである。
  • 記号列counterと記号列exampleの連接はcounterexampleである。
  • 記号列Ultraと記号列sevenの連接はUltrasevenである。
  • 記号列Bicycleと記号列Repairmanの連接はBicycleRepairmanである。
  • 記号列 $\varepsilon$ と記号列 $\varepsilon$ の連接は $\varepsilon$ である。

連接とモノイド

  • 連接 $\cdot$ を $\Sigma^{*}$ 上の演算とみなすことで、$(\Sigma^{*}, \cdot)$ はモノイドになる。単位元は $\varepsilon$ である。
    • 特に $(\Sigma^{*}{,}\ \cdot)$ を $\Sigma$ が生成する自由モノイドという。

鏡像

鏡像の定義

$\Sigma^{*}$ の元 $w$ の 鏡像(mirror image) $\overleftarrow{w}$ を次のように帰納的に定義する。

  1. $w=\varepsilon$ のとき、$\overleftarrow{w}=\varepsilon$ である。
  2. $w=av$ のとき、$\overleftarrow{w}=\overleftarrow{v}a$ である。

鏡像の例

  • 記号列mathpediaの鏡像はaidephtamである。
  • 記号列tomatoの鏡像はotamotである。
  • 記号列dogの鏡像はgodである。
  • 記号列topの鏡像はpotである。
  • 記号列lolの鏡像はlolである。

鏡像の性質

  • $\overleftarrow{\overleftarrow{w}}=w$

商の定義

$\Sigma$ 上の形式言語 $L$、文字列 $w \in \Sigma^{*}$ に対して $L$ の $w$ による左商(left quotient)を $$w^{-1}L := \left\{ v \in \Sigma^{*} \left| wv \in L \right. \right\}$$ と定める。

また、$L$ の $w$ による右商(right quotient)を $$Lw^{-1} := \left\{ v \in \Sigma^{*} \left| vw \in L \right. \right\}$$ と定める。

形式言語 $L$ の左商全体の集合を ${\Sigma^{*}}^{-1}L$ 右商全体の集合を $L{\Sigma^{*}}^{-1}$ で表す。つまり、 $${\Sigma^{*}}^{-1}L := \left\{ w^{-1}L \left| w \in \Sigma^{*} \right. \right\}$$ $$L{\Sigma^{*}}^{-1} := \left\{ Lw^{-1} \left| w \in \Sigma^{*} \right. \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$ の数え上げ関数)。

参考文献

  1. 新屋 良磨、オートマトン理論再考、コンピュータ ソフトウェア、2017、34 巻、3 号、p. 3_3-3_35、公開日 2017/09/25、Print ISSN 0289-6540、https://doi.org/10.11309/jssst.34.3_3https://www.jstage.jst.go.jp/article/jssst/34/3/34_3_3/_article/-char/ja
  2. 五十嵐喜英他、『数理情報科学シリーズ 24 オートマトンと形式言語の基礎?』、牧野書店、2011

関連項目



トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2020-10-04 (日) 21:55:43 (24d)