オートマトンと言語理論
文字列学
文字列を記号で表す
まずアルファベット全体を定義する
言語に含まれるアルファベットの集合を $ \Sigmaとする
例えば$ \Sigma = \{ a, b \}とすると言語には"a", "b"の文字があることになる
$ wは文字列(語)
$ w=a_1 a_2 a_3 \ldots a_n
$ a_n \in \Sigma
$ \Sigma^nはn文字の文字列全体の集合を表す
$ \Sigma^n = \{ s_1 s_2 s_3, \ldots, s_n \mid s_i \in \Sigma, i=1,2...n \}
↑のように定義できる
例えば $ \Sigma^2 = \{ aa, ab, ba, bb \}
$ n=0の場合
$ \Sigma^0 = \{ \epsilon \}
$ \epsilonは空文字を表す
$ \Sigma^*は"a", "b"で表せる全ての文字列 (=$ w)の集合
$ Kleene閉包
$ \Sigma^* = \bigcup_{k=0}{\Sigma^k} = \{ \epsilon \} \cup \Sigma^1 \cup \Sigma^2 \cup \dots \cup \Sigma^k
つまり$ \Sigma^* = \{ \epsilon, "a", "b", "aa", "ab",\ldots \}
任意の文字列は$ \Sigma^*に属する ($ w \in \Sigma^*)
$ \Sigma^1 = \Sigma
一文字で表せる全ての文字列の集合 = アルファベットの集合
任意の文字列の長さは$ |w|と表す
文字列$ x, yがある時、$ xy(連接)と表す
$ |xy| = |x| + |y|
あたりまえ体操
語$ wが語$ xの接頭辞 or 接尾辞である時の表記
接頭辞: 語$ y \in \Sigma^*について$ x = wyである
$ w \sqsubset x
接尾辞: 語 $ y \in \Sigma^*について$ x = ywである
$ w \sqsupset x
$ |y| > 0の時それぞれ 真の{ 接尾辞, 接頭辞}とよぶ
有限オートマトン (FA)
有限個の内部状態があるので有限オートマトン
FAにはいくつかの種類がある
DFA (決定性FA)
NFA (非決定性FA)
ε-NFA (ε遷移する非決定性FA)
それぞれのFAは全て同等 = 相互変換が可能
DFA (決定性有限オートマトン)
有限個の内部状態をもち、ヘッドが入力文字列を一字ずつ読み取る
入力を読み切った時の最終状態が受理集合のどれかに到達していれば受理
定義
$ M= (Q, \Sigma, \delta, q_0, F)
$ Q
状態を表す有限個の集合
内部状態を$ qとおくと、必ず$ q \in Q
$ \Sigma
入力されるアルファベットの集合
入力を$ xとすると$ x \in \Sigma^*
$ \delta
遷移関数
入力文字列 $ x = a_1 a_2 a_3とする
状態$ pにある時,文字$ a \in \Sigmaが入力されるとどの状態$ q \in Qに遷移するか決める
$ \delta(p \in Q, a \in \Sigma) \rarr p' \in Q
$ \delta(q_0, x) = \delta(\delta(\delta(q_0, a_1), a_2), a_3) 拡張する
$ q_0
初期状態
$ q_0 \in Q
$ F
受理状態
$ F \in Q
$ Mの状態$ qが$ q \in Fの時機械は入力を受理する
DFA $ M = (Q, \Sigma, \delta, q_0, F)に受理される$ \Sigma上の語全体を表す集合
$ L(M) = \{ w \in \Sigma^* \mid \delta(q_0, w) \in F \}
($ wはKleene閉包に含まれていて、かつ受理状態に達するもの)
$ L \subseteq \Sigma^*($ Lは言語)の時、$ L = L(M)であるDFAが存在するとき
$ Lを正規言語という
DFAで受理できる語の集合...(?)