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 'a'} = {a, aa, aaa, abb, abbb, ababb} <strong>Infinite Language</strong>