Aritalab:Lecture/Automata

形式言語理論

タンパク質は塩基やアミノ酸の列（すなわち記号列）が並んだものとみなすことができます。 「自然界に存在する記号列に規則性などないだろう」と思う人も多いでしょうが、タンパク質の翻訳はコドン表という正則言語を使って書かれています。 また真核生物の遺伝子構造はエキソンとイントロンの繰り返しが非コード領域に挟まれたもので、これも正則言語で記述できます。 文字列の中に「構造」が観察される場合、こうした構造の複雑さの程度を理論的に解析するのが形式言語理論です。ここでは以下の概念を簡単に説明しています。

1. 形式言語トップ
2. 準備
3. 正則言語　(正規言語）
4. 文脈自由言語
5. プッシュダウンオートマトン
6. チューリング機械
7. クラスNP

よく知りたい人のために

言語理論の教科書は何といっても以下の 2 冊でしょう。

• オートマトン 言語理論 計算論 I　(Hopcroft, Motwani, Ullman)
• オートマトン 言語理論 計算論 II (Hopcroft, Motwani, Ullman)