オートマトン理論は、コンピューター サイエンスと数学の理論分野です。それは抽象的なマシンと、これらのマシンを使用して解決できる計算問題の研究です。抽象的な機械はオートマトンと呼ばれます。オートマトン理論の開発の背後にある主な動機は、離散システムの動的挙動を記述および分析する方法を開発することでした。
このオートマトンは状態と遷移で構成されます。の 州 で表されます サークル 、 そしてその トランジション で表されます 矢印 。
オートマトンは、何らかの文字列を入力として受け取る種類のマシンであり、この入力は有限数の状態を経て、最終状態に入る可能性があります。
オートマトンで頻繁に使用される重要な基本用語があります。
記号:
シンボルは、任意の文字、アルファベット、または任意の絵であるエンティティまたは個別のオブジェクトです。
例：
1、a、b、#
アルファベット:
アルファベットは有限の記号の集合です。それは∑で表されます。
例:
∑ = {a, b} ∑ = {A, B, C, D} ∑ = {0, 1, 2} ∑ = {0, 1, ....., 5] ∑ = {#, β, Δ} 弦：
これは、アルファベットの記号の有限のコレクションです。文字列は w で表されます。
例 1:
∑ = {a, b} の場合、∑ から生成できるさまざまな文字列は {ab, aa, aaa, bb, bbb, ba, aba....} となります。
- シンボルの出現がゼロの文字列は、空の文字列と呼ばれます。 εで表されます。
- 文字列 w 内のシンボルの数を文字列の長さと呼びます。これは |w| で表されます。
例 2:
w = 010 Number of Sting |w| = 3
言語：
言語は適切な文字列の集合です。 Σ 上で形成される言語は次のようになります。 有限の または 無限 。
例: 1
L1 = {Set of string of length 2} = {aa, bb, ba, bb} <strong>Finite Language</strong> 例: 2
L2 = {Set of all strings starts with 'a'} = {a, aa, aaa, abb, abbb, ababb} <strong>Infinite Language</strong>