Introduzione alla teoria degli automi

Automi: che cos'è?

Il termine "automi" deriva dalla parola greca "αὐτόματα" che significa "auto-agente". Un automa (Automata al plurale) è un dispositivo informatico semovente astratto che segue automaticamente una sequenza predeterminata di operazioni.

Un automa con un numero finito di stati è chiamato a Finite Automaton (FA) o Finite State Machine (FSM).

Definizione formale di un automa finito

Un automa può essere rappresentato da una tupla di 5 (Q, ∑, δ, q 0 , F), dove -

  • Q è un insieme finito di stati.

  • ∑ è un insieme finito di simboli, chiamato alphabet dell'automa.

  • δ è la funzione di transizione.

  • q0è lo stato iniziale da cui viene elaborato qualsiasi input (q 0 ∈ Q).

  • F è un insieme di stati finali di Q (F ⊆ Q).

Terminologie correlate

Alfabeto

  • Definition - An alphabet è un insieme finito di simboli.

  • Example - ∑ = {a, b, c, d} è un alphabet set dove sono "a", "b", "c" e "d" symbols.

Corda

  • Definition - A string è una sequenza finita di simboli presi da ∑.

  • Example - 'cabcad' è una stringa valida nel set alfabetico ∑ = {a, b, c, d}

Lunghezza di una stringa

  • Definition- È il numero di simboli presenti in una stringa. (Denotato da|S|).

  • Examples -

    • Se S = 'cabcad', | S | = 6

    • Se | S | = 0, viene chiamato un empty string (Denotato da λ o ε)

Kleene Star

  • Definition - La star di Kleene, ∑*, è un operatore unario su un insieme di simboli o stringhe, ∑, che fornisce l'insieme infinito di tutte le possibili stringhe di tutte le lunghezze possibili ∑ Compreso λ.

  • Representation- ∑ * = ∑ 0 ∪ ∑ 1 ∪ ∑ 2 ∪ ……. dove ∑ p è l'insieme di tutte le possibili stringhe di lunghezza p.

  • Example - Se ∑ = {a, b}, ∑ * = {λ, a, b, aa, ab, ba, bb, ……… ..}

Chiusura Kleene / Plus

  • Definition - Il set ∑+ è l'insieme infinito di tutte le possibili stringhe di tutte le lunghezze possibili su ∑ escluso λ.

  • Representation- ∑ + = ∑ 1 ∪ ∑ 2 ∪ ∑ 3 ∪ …….

    ∑ + = ∑ * - {λ}

  • Example- Se ∑ = {a, b}, ∑ + = {a, b, aa, ab, ba, bb, ……… ..}

linguaggio

  • Definition- Una lingua è un sottoinsieme di ∑ * per alcuni alfabeti ∑. Può essere finito o infinito.

  • Example - Se la lingua accetta tutte le possibili stringhe di lunghezza 2 su ∑ = {a, b}, allora L = {ab, aa, ba, bb}