Definizioni

Automa a stati finiti deterministico (DFA)

Symbol	Meaning
Q	finite set called the States
Σ	finite state called Alphabet
δ:QxΣ→Q	transition function
q0∈Q	start state
F⊆Q	Set of accepted states

Linguaggio regolare

Un linguaggio è detto linguaggio regolare se è riconosciuto da un automa a stati finiti.

Operazioni regolari

Siano A e B due linguaggi. Definiamo le operazioni regolari unione, concatenazione e star così:

• Union: A ∪ B = {x|x∈A or x∈B}
• Concatenation: A ○ B = {xy | x∈A and y∈B}
• Star: A* = {x₁, x₂, x₃,...x_k | k ≥ 0 and each x_i∈A }

Inoltre si definisce per prassi ε stringa vuota (in maniera simile a quello che in SQL è NULL)

Automa a stati finiti non deterministico (NFA)

Symbol	Meaning
Q	finite set called the States
Σ	finite state called Alphabet
δ:QxΣε→P(Q)	transition function
q0∈Q	start state
F⊆Q	Set of accepted states

Espressione regolare

Un'espressione regolare può essere

• a per qualche a nell'alfabeto Σ
• ε
• ∅
• (R₁∪R₂), con R₁, R₂ espressioni regolari
• (R₁○R₂), con R₁, R₂ espressioni regolari
• (R₁^*), con R₁ espressione regolare

Se u, v, w sono stringhe di variabili e terminali, e A → v è una regola della grammatica, diciamo che uAv produce uwv, scritto uAv ⇒ uwv.

Diciamo che u deriva v, scritto

$u\stackrel{*}{\Rightarrow }v$

se u = v oppure se esiste una sequenza, con k ≥ 0, u₁ ⇒ u₂ ⇒ u₃ ⇒ ...u_k ⇒ v.

Grammatica context-free (CFG)

V	Un insieme finito di variabili
Σ	Un insieme finito, disgiunto da V, di terminali
R	Un insieme finito di regole, ciascuna costituita da una variabile e una stringa di variabili e terminali
S∈V	La variabile di partenza

Forma normale di Chomsky

Una grammatica context-free è in forma normale di Chomsky se ogni regola è nella forma

A → BC

A → a

dove a è ogni terminale e A, B, C sono ogni variabile, eccetto che B e C non sono variabili di partenza. In aggiunta, permettiamo la regola S → ε, dove S è la variabile di partenza.

Pushdown automa

Symbol	Meaning
Q	finite set called the States
Σε	input Alphabet
Γε	stack Alphabet
δ:QxΣεxΓε→P(Q, Γε)	transition function
q0∈Q	start state
F⊆Q	Set of accepted states

Macchina di Turing

Una macchina di Turing è una 7-tupla, (Q, Σ, Γ, δ, q₀, q_accepted, q_rejected), dove Q, Σ, Γ sono tutti insiemi finiti e

Symbol	Meaning
Q	insieme finito di stati
Σ	alfabeto che non contiene il simbolo "blank" ˽
Γ	alfabeto del nastro, dove ˽ ∈ Γ e Σ ⊆ Γ
δ:QxΓ→Q x Γ x {L, R}	funzione di transizione
q0∈Q	stato di partenza
qaccepted	stato accettato
qrejected	stato rifiutato

Con q_accepted ≠ q_rejected