旅する情報系大学院生

旅と留学とプログラミング

形式言語とオートマトン、チューリングマシンの関係について

雑です。手書きです。
何かあればコメントしていただきたいです。


全体としてこんなイメージ。
f:id:yamaguchi_1024:20160611114112j:plain


形式言語の文法は、G=<N,Σ,P,S>のように表され、Nは非終端記号、Σは終端記号、Pが生成規則、Sが初期記号となっている。

正規言語が有限オートマトンと等価である。
正規言語の文法は、例えばG=<{S},{a,b},{S->aS,S->bS,S->a,S->b},S>
この規則からは、初期記号がSなので例えば
S->aS->aaS->aabS->aabaなどが生成する。この規則はaかbから始まる任意の長さの文字列を生成する。
これを受理するオートマトンは、例えば以下の図のようなもの。(訂正しました)
f:id:yamaguchi_1024:20160612014923j:plain

しかし、有限オートマトンでは、aがn個あってbがn個あるようなa**n b**nだけ受理して他は受理しないようなオートマトンを作ることはできず、これを実現できるプッシュダウンオートマトンと等価なのが文脈自由言語である。
文脈自由言語の文法は、例えばG=<{S},{a,b},{S->aSb,S->ab},S>
この規則からは、
S->aSb->aaSbb->aaaSbbb->aaaabbbb
などが生成する。
これを受理するプッシュダウンオートマトンは、普通のオートマトンにスタックを付けたものであり、例えば下図のオートマトンで受理することができる。
f:id:yamaguchi_1024:20160611114234j:plain

しかしプッシュダウンオートマトンではa**n b**n c**n の文字列を受理して他を受理しないようなオートマトンを作ることはできず、これを実現できる線形拘束オートマトン(チューリングマシンのテープが有限なもの)と等価なのが文脈依存言語である。
文脈依存言語の文法は例えば、G=<{S},{a,b},{S->aSBC, aB->ab, S->aBC, bB->bb, CB->AB, bC->bc, AB->AC,cC->cc,AC->BC},S>
である。
この規則からは例えば、
S->aSBC->aaBCBC->aabCBC->aabABC->aabACC->aabBCC->aabbCC->aabbcC->aabbccが生成する。
これは線形拘束オートマトンによって受理される。

これまでの文法規則だと文字列を伸ばすことはできても縮めることはできない。
句構造言語は制限がなくどんな文字でも生成できるので、aaabb->aなどを規則にすることで文字列を自由に操ることができる。
これを受理するのがチューリングマシンである。


オートマトンとチューリングマシンの関係のイメージを下図に示す。
f:id:yamaguchi_1024:20160611114300j:plain