Aritalab:Lecture/Automata
From Metabolomics.JP
形式言語理論
タンパク質は塩基やアミノ酸の列(すなわち記号列)が並んだものとみなすことができます。 「自然界に存在する記号列に規則性などないだろう」と思う人も多いでしょうが、タンパク質の翻訳はコドン表という正規言語を使って書かれています。 また真核生物の遺伝子構造はエキソンとイントロンの繰り返しが非コード領域に挟まれたもので、これも正規言語で記述できます。 このように文字列に「構造」が観察される場合、こうした構造の複雑さの程度を理論的に解析するのが言語理論です。ここでは以下の概念を簡単に説明しています。
よく知りたい人のために
言語理論の教科書は何といっても以下の 2 冊でしょう。
- オートマトン 言語理論 計算論 I (Hopcroft, Motwani, Ullman)
- オートマトン 言語理論 計算論 II (Hopcroft, Motwani, Ullman)