Wprowadzenie do teorii automatów
Automata - co to jest?
Termin „automata” pochodzi od greckiego słowa „αὐτόματα”, które oznacza „samoczynne działanie”. Automat (w liczbie mnogiej Automata) to abstrakcyjne samobieżne urządzenie obliczeniowe, które automatycznie wykonuje z góry określoną sekwencję operacji.
Automat ze skończoną liczbą stanów nazywany jest a Finite Automaton (FA) lub Finite State Machine (FSM).
Formalna definicja automatu skończonego
Automat można przedstawić jako 5-krotkę (Q, ∑, δ, q 0 , F), gdzie -
Q jest skończonym zbiorem stanów.
∑ jest skończonym zbiorem symboli, zwanym alphabet automatu.
δ jest funkcją przejścia.
q0jest stanem początkowym, z którego przetwarzane jest dowolne wejście (q 0 ∈ Q).
F jest zbiorem stanu / stanów końcowych Q (F ⊆ Q).
Powiązane terminologie
Alfabet
Definition - An alphabet to dowolny skończony zbiór symboli.
Example - ∑ = {a, b, c, d} jest an alphabet set gdzie „a”, „b”, „c” i „d” są symbols.
Strunowy
Definition - A string jest skończonym ciągiem symboli pobranych z ∑.
Example - „cabcad” jest prawidłowym ciągiem w zestawie alfabetu ∑ = {a, b, c, d}
Długość sznurka
Definition- Jest to liczba symboli obecnych w ciągu. (Oznaczony przez|S|).
Examples -
Jeśli S = 'cabcad', | S | = 6
Jeśli | S | = 0, nazywa się to empty string (Oznaczony przez λ lub ε)
Kleene Star
Definition - Gwiazda Kleene, ∑*, jest operatorem jednoargumentowym na zbiorze symboli lub łańcuchów, ∑, co daje nieskończony zbiór wszystkich możliwych ciągów o wszystkich możliwych długościach ∑ włącznie z λ.
Representation- ∑ * = ∑ 0 ∪ ∑ 1 ∪ ∑ 2 ∪ ……. gdzie ∑ p jest zbiorem wszystkich możliwych ciągów o długości p.
Example - Jeśli ∑ = {a, b}, ∑ * = {λ, a, b, aa, ab, ba, bb, ……… ..}
Zamknięcie Kleene / Plus
Definition - Komplet ∑+ jest nieskończonym zbiorem wszystkich możliwych ciągów o wszystkich możliwych długościach powyżej ∑ z wyłączeniem λ.
Representation- ∑ + = ∑ 1 ∪ ∑ 2 ∪ ∑ 3 ∪ …….
∑ + = ∑ * - {λ}
Example- Jeśli ∑ = {a, b}, ∑ + = {a, b, aa, ab, ba, bb, ……… ..}
Język
Definition- Język to podzbiór ∑ * dla jakiegoś alfabetu ∑. Może być skończona lub nieskończona.
Example - Jeśli język przyjmuje wszystkie możliwe ciągi o długości 2 ponad ∑ = {a, b}, to L = {ab, aa, ba, bb}