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}