Automata-theory-introduction

オートマトン理論の紹介

オートマトン-それは何ですか？

「オートマタ」という用語は、ギリシャ語の「αὐτόματα」に由来し、「自己作用」を意味します。 オートマトン（複数のオートマトン）は、あらかじめ決められた一連の操作を自動的に実行する抽象的な自走式コンピューティングデバイスです。

有限数の状態を持つオートマトンは、 Finite Automaton （FA）または Finite State Machine （FSM）と呼ばれます。

有限オートマトンの正式な定義

オートマトンは5タプル（Q、∑、δ、q〜0〜、F）で表すことができます。ここで、

• Q は有限状態のセットです。
• ∑ は、オートマトンの alphabet と呼ばれる有限のシンボルセットです。
• *δ*は遷移関数です。
• * q〜0〜*は、入力が処理される初期状態です（q〜0〜∈Q）。
• F は、Qの最終状態の状態です（F⊆Q）。

関連用語

アルファベット

• 定義-*アルファベット*は、シンボルの有限セットです。
• 例-∑ = \ {a、b、c、d}は*アルファベットセット*で、「a」、「b」、「c」、「d」は*記号*です。

ひも

• 定義-*文字列*はaから取られたシンボルの有限シーケンスです。
• 例-「cabcad」はアルファベットセットの有効な文字列です∑ = \ {a、b、c、d}

ひもの長さ

• 定義-文字列に存在するシンボルの数です。 （ | S | で示されます）。
• 例-
• S = 'cabcad’の場合、| S | = 6
• | S | = 0の場合、それは*空の文字列*（*λ*または*ε*で示される）と呼ばれます

クリーネスター

• Definition -Kleene star、 ∑ は、記号または文字列のセットの単項演算子 *∑ で、λ*を含む *∑ を超えるすべての可能な長さのすべての可能な文字列の無限集合を与えます。 。
• 表現-∑ * = ∑〜0〜∪∑〜1〜∪∑〜2〜∪……。 ここで、∑〜p〜は、長さpのすべての可能な文字列のセットです。
• 例-∑ = \ {a、b}、If * = \ {λ、a、b、aa、ab、ba、bb、………..}の場合

クリーネ閉鎖/プラス

• 定義-セット ∑ ^ + ^ は、λを除くoverを超えるすべての可能な長さのすべての可能な文字列の無限のセットです。
• 表現-∑ ^ + ^ = ∑〜1〜∪∑〜2〜∪∑〜3〜∪……。 + ∑ ^ + ^ = ∑ * − \ {λ}
• 例-∑ = \ {a、b}、If ^ + ^ = \ {a、b、aa、ab、ba、bb、………..}の場合

言語

• 定義-言語はいくつかのアルファベットalphabetの∑ *のサブセットです。 有限または無限の可能性があります。
• 例-言語が∑ = \ {a、b}で長さ2のすべての可能な文字列を取る場合、L = \ {ab、aa、ba、bb}