オートマトン理論の紹介
Automata –それはなんですか？
「オートマタ」という用語は、「自己作用」を意味するギリシャ語の「αὐτόματα」に由来しています。オートマトン（複数形のオートマトン）は、あらかじめ決められた一連の操作を自動的に実行する抽象的な自走式コンピューティングデバイスです。
有限数の状態を持つオートマトンは、 Finite Automaton （FA）または Finite State Machine （FSM）。
有限オートマトンの正式な定義
オートマトンは、5タプル（Q、∑、δ、q 0、F）で表すことができます。ここで、−
Q は有限の状態のセットです。
∑ は、と呼ばれる有限の記号セットです。 alphabet オートマトンの。
δ 遷移関数です。
q0任意の入力が処理されるから初期状態である（Q 0 ∈Q）。
F Qの最終状態/状態のセットです（F⊆Q）。
関連用語
アルファベット
Definition − alphabet 記号の有限集合です。
Example − ∑ = {a、b、c、d}は alphabet set ここで、「a」、「b」、「c」、および「d」は symbols。
ストリング
Definition − a string ∑から取得したシンボルの有限シーケンスです。
Example −'cabcad 'は、アルファベットセットの有効な文字列です∑ = {a、b、c、d}
文字列の長さ
Definition−文字列に存在する記号の数です。（によって示される|S|）。
Examples −
S = 'cabcad'の場合、| S | = 6
| S | = 0の場合、それは empty string （によって示される λ または ε）
クリーネ閉包
Definition −クリーネ閉包、 ∑*は、記号または文字列のセットに対する単項演算子です。 ∑、これにより、可能なすべての長さのすべての可能な文字列の無限セットが得られます。 ∑ 含む λ。
Representation- Σ* =Σ 0 ∪Σ 1 ∪Σ 2 ∪...。どこΣのpは長さpのすべての可能な文字列の集合です。
Example − ∑ = {a、b}の場合、∑ * = {λ、a、b、aa、ab、ba、bb、………..}
クリーネ閉包/プラス
Definition −セット ∑+ は、λを除く∑を超えるすべての可能な長さのすべての可能な文字列の無限集合です。
Representation- Σ + =Σ 1 ∪Σ 2 ∪Σ 3 ∪...。
∑ + = ∑ * − {λ}
Example− ∑ = {a、b}、∑ + = {a、b、aa、ab、ba、bb、………..}の場合
言語
Definition−言語は、一部のアルファベット∑の∑ *のサブセットです。有限でも無限でもかまいません。
Example −言語が∑ = {a、b}で長さ2の可能なすべての文字列を使用する場合、L = {ab、aa、ba、bb}