Concetti Fondamentali di Automi Finiti e Linguaggi Regolari

Definizioni Fondamentali

Automa Finito Non Deterministico (AFN)

Un insieme di stati e gruppi di transizioni da stato a stato, che accettano input su simboli tratti da un alfabeto.

Linguaggio

È un insieme di parole (stringhe) di lunghezza finita, formato da un alfabeto finito.

Espressione Regolare (Regular Expression)

È un modo per rappresentare i linguaggi regolari usando caratteri alfabetici che definiscono il linguaggio.

Operazioni su Stringhe e Linguaggi

Concatenazione

L'operazione di concatenazione è la combinazione di due stringhe o sequenze di caratteri.

Esempi di Concatenazione:

• 'z' concatenato a '132' = "Z132"
• '456' concatenato a 'AB' = "456AB"
• 'Z' concatenato a 'A' = "ZA"

Alfabeto

È un insieme finito e ordinato di simboli (grafemi) utilizzati per rappresentare un linguaggio. Serve come sistema di comunicazione e, in matematica, è definito come un insieme finito e ordinato di simboli.

Stringa (Catena)

Una stringa (o parola) è una sequenza ordinata di lunghezza arbitraria (ma finita) di elementi appartenenti a un alfabeto definito.

Chiusura di Kleene (Kleene Star)

Se $A$ è un linguaggio su un alfabeto, la chiusura di Kleene è definita come segue:

$$A^* = \bigcup_{n=0}^{\infty} A^n$$

Ciò significa che il carattere può apparire in una stringa 0, 1, o infinite volte.

Chiusura Positiva

È definita come segue:

$$A^+ = \bigcup_{n=1}^{\infty} A^n$$

Ciò indica che il carattere deve apparire almeno una volta.

Esempio:

Ad esempio: "ho la +" genera: hi, Hoola, hooola...

Automi e Grammatiche

Macchina a Stati Finiti (Automa)

L'automa a stati finiti è un modello matematico di un sistema con ingressi e uscite discreti.

Definizione di Linguaggio e Grammatica

Il linguaggio generato dalla grammatica $G$ è:

$$L(G) = \{x \mid x \text{ è } (w, z)^n \text{ per } n \text{ da } 1 \text{ a infinito}\}$$

Regole di Produzione Iniziali:

| -> Sono:
X | - sequenza>
Stream | - Wyz>
Stream | - sequenza Wyz>

Componenti della Grammatica $G$:

• $G = (V, N, V_0, \mid \rightarrow)$
• $V = \text{Sole}$ (Simboli Terminali)
• $S = \{w, z\}$ (Alfabeto)
• $N = \{V_0, \text{sequenze}\}$ (Simboli Non Terminali)
• $V_0 = V_0$ (Simbolo Iniziale)

Esempio di Grammatica per Numeri Decimali

(Nota: La sequenza LG = (950, .85,830.20,0, .79,1.5 ...) sembra essere un esempio di output o una lista di valori non correlata alla grammatica sottostante.)

Regole di Produzione:

V0 -> numero decimale
Numero decimale -> Unsigned
Numero decimale -> Frazione decimale
Numero decimale -> Decimale senza segno
Frazione decimale -> Unsigned
Unsigned -> Cifra
Unsigned -> Cifra Unsigned
Cifre -> 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

Componenti della Grammatica $G$:

• $G = (V, N, V_0, \rightarrow)$
• $V = \text{Simboli Terminali}$ (Vuoto nell'originale)
• $S = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$ (Alfabeto/Simboli Terminali)
• $N = \{V_0, \text{numero decimale, decimale, senza segno, cifra}\}$ (Simboli Non Terminali)
• $V_0 = V_0$ (Simbolo Iniziale)