Teoria automatów jest teoretyczną gałęzią informatyki i matematyki. Jest to badanie abstrakcyjnych maszyn i problemów obliczeniowych, które można rozwiązać za pomocą tych maszyn. Maszyna abstrakcyjna nazywana jest automatem. Główną motywacją do opracowania teorii automatów było opracowanie metod opisu i analizy dynamicznego zachowania systemów dyskretnych.

Automat ten składa się ze stanów i przejść. The Państwo jest reprezentowany przez koła , oraz Przejścia jest reprezentowany przez strzałki .

Automaty to rodzaj maszyny, która przyjmuje na wejściu jakiś ciąg znaków, który przechodzi przez skończoną liczbę stanów i może wejść w stan końcowy.

Istnieją podstawowe terminologie, które są ważne i często używane w automatach:

Symbolika:

Symbole to byt lub pojedyncze obiekty, które mogą być dowolną literą, alfabetem lub dowolnym obrazem.

Przykład:

1, a, b, #

Alfabety:

Alfabety to skończony zbiór symboli. Jest to oznaczone przez ∑.

Przykłady:

 ∑ = {a, b} ∑ = {A, B, C, D} ∑ = {0, 1, 2} ∑ = {0, 1, ....., 5] ∑ = {#, β, Δ} 

Strunowy:

Jest to skończony zbiór symboli z alfabetu. Ciąg jest oznaczony przez w.

Przykład 1:

Jeśli ∑ = {a, b}, różne ciągi, które można wygenerować z ∑ to {ab, aa, aaa, bb, bbb, ba, aba.....}.

• Ciąg znaków, w którym nie ma żadnych symboli, nazywany jest ciągiem pustym. Jest reprezentowany przez ε.
• Liczba symboli w ciągu w nazywana jest długością ciągu. Jest oznaczony przez |w|.

Przykład 2:

 w = 010 Number of Sting |w| = 3 

Język:

Język to zbiór odpowiednich ciągów znaków. Może być język utworzony na podstawie Σ Skończone Lub Nieskończony .

Przykład 1

 L1 = {Set of string of length 2} = {aa, bb, ba, bb} <strong>Finite Language</strong> 

Przykład: 2

 L2 = {Set of all strings starts with &apos;a&apos;} = {a, aa, aaa, abb, abbb, ababb} <strong>Infinite Language</strong>