Fondamenti di Informatica I – Teoria degli Automi e dei Linguaggi

Flashcard di stile domanda-risposta sui concetti chiave di algoritmi, problemi, modelli di calcolo, linguaggi formali, grammatiche, automi finiti, espressioni regolari, pumping lemma, chiusura dei linguaggi, PDA e forme normali delle grammatiche.

Che cos’è un algoritmo?

Una sequenza finita di passi ben definiti che risolve un problema, con finitudine, determinismo, effettività, ingressi e uscite.

Qual è la differenza tra problema computazionale e algoritmo?

Il problema computazionale è la funzione astratta da calcolare; l’algoritmo è la procedura concreta che risolve un’istanza del problema.

Quando un problema è decidibile?

Quando esiste un algoritmo che lo risolve in tempo finito per ogni possibile input.

Cosa distingue problemi trattabili da intrattabili?

I trattabili hanno algoritmi a tempo polinomiale (classe P), gli intrattabili richiedono tempo super-polinomiale (es. NP-completi).

Quale modello di calcolo è il riferimento fondamentale per la computabilità?

La Macchina di Turing.

Che cos’è un linguaggio formale?

Un insieme (possibilmente infinito) di stringhe su un alfabeto finito.

Definisci operazione di stella di Kleene su un linguaggio L.

L* è l’insieme di tutte le concatenazioni finite (inclusa la stringa vuota) di parole di L.

Da quali componenti è composta una grammatica formale G = (V, Σ, R, S)?

Simboli non terminali V, terminali Σ, regole di produzione R, simbolo iniziale S.

Qual è il livello più potente della gerarchia di Chomsky?

Il Tipo 0 (grammatiche libere), che genera i linguaggi ricorsivamente enumerabili.

Quale automa riconosce i linguaggi regolari (Tipo 3)?

L’automa a stati finiti deterministico o non deterministico (DFA/NFA).

Che cos’è la powerset construction?

Procedura che trasforma un NFA in un DFA usando come stati del DFA i sottoinsiemi degli stati dell’NFA.

Quando un DFA accetta una stringa w?

Se, partendo dallo stato iniziale, dopo aver letto tutta w si trova in uno stato finale.

Che cos’è una configurazione di un automa?

Fotografia dello stato attuale: stato interno, input rimanente (e contenuto dei nastri/pila se presenti).

Definizione formale di DFA.

Quintupla (Q, Σ, δ, q₀, F) con Q stati, Σ alfabeto, δ funzione di transizione, q₀ stato iniziale, F stati finali.

Cosa rende un NFA non deterministico?

Almeno una configurazione ha più di una transizione possibile (anche ε-transizioni).

Condizione di accettazione di un NFA.

Esiste almeno una computazione che porta dallo stato iniziale a uno stato finale consumando tutto l’input.

Qual è la relazione di potere espressivo fra DFA e NFA?

Sono equivalenti: riconoscono esattamente gli stessi linguaggi regolari.

Definisci ε-chiusura di uno stato q.

L’insieme di tutti gli stati raggiungibili da q tramite sole transizioni ε, incluso q stesso.

Come si trasforma un ε-NFA in un NFA senza ε?

Calcolando l’ε-chiusura di ogni stato, aggiornando le transizioni e i set di stati finali.

Quando due grammatiche G1 e G2 sono equivalenti?

Quando generano lo stesso linguaggio: L(G1) = L(G2).

Forma delle produzioni in una grammatica regolare destra-lineare.

A → aB, A → a oppure A → ε (A,B non terminali, a terminale).

Passi per convertire una grammatica regolare in un DFA.

Ogni non terminale → stato; S → stato iniziale; produzioni A→aB trasformate in transizioni etichettate da a; A→a o ε definiscono stati finali.

Quali sono gli operatori base nelle espressioni regolari?

Unione (|), concatenazione, chiusura di Kleene (*).

Enunciato del Pumping Lemma per linguaggi regolari.

Esiste p≥1 tale che ogni stringa w∈L con |w|≥p può essere divisa w=xyz con |xy|≤p, |y|≥1 e xyⁱz∈L per ogni i≥0.

Perché il linguaggio {aⁿbⁿ | n≥0} non è regolare (uso del pumping lemma)?

Per w=aᵖbᵖ la parte pompabile y contiene solo ‘a’; pompando otteniamo più ‘a’ che ‘b’, fuori dal linguaggio → contraddizione.

Enunciato del Pumping Lemma per linguaggi context-free.

Esiste p≥1 tale che ogni w∈L con |w|≥p si scrive w=uvxyz con |vxy|≤p, |vy|≥1 e uvⁱxyⁱz∈L per ogni i≥0.

Che cosa dimostra il linguaggio {aⁿbⁿcⁿ} riguardo ai CF?

Non è context-free (dal pumping lemma CF).

Operazioni di chiusura dei linguaggi regolari.

Chiusi sotto unione, intersezione, complemento, concatenazione, stella di Kleene.

Come si ottiene il complemento di un linguaggio regolare?

In un DFA completo si scambiano stati finali e non finali.

Prodotto cartesiano di due DFA: a cosa serve?

A costruire un DFA che riconosce l’intersezione dei due linguaggi.

Quando la stella di Kleene di un linguaggio regolare è regolare?

Sempre; basta aggiungere ε-transizioni dallo stato iniziale e dai finali per ricominciare la computazione.

Cos’è la minimizzazione di un DFA?

Processo che fonde stati indistinguibili e rimuove quelli non raggiungibili, ottenendo il DFA con il minimo numero di stati.

Perché i linguaggi regolari hanno predicati decidibili su vuoto/finito/infinito?

Perché i DFA sono finiti: si può analizzare il grafo degli stati per cicli e raggiungibilità di stati finali.

Cosa aggiunge un PDA rispetto a un DFA?

Una memoria stack (pila) che permette di riconoscere linguaggi context-free.

Forma generale di una transizione di PDA.

δ(q, a/ε, Z) ⊆ Q × Γ* : con stato q, simbolo di input a (o ε) e simbolo di pila Z, si passa a un nuovo stato e si sostituisce Z con una stringa di pila.

Due criteri di accettazione per PDA.

Per pila vuota (N(M)) o per stato finale (L(M)).

Forma Normale di Chomsky (CNF) – quali produzioni ammette?

Solo A→BC o A→a (più eventualmente S→ε se ε∈L(G)).

Forma Normale di Greibach (GNF) – struttura di produzione.

A→aβ con a terminale e β sequenza (anche vuota) di non terminali.

Perché i linguaggi CF non sono chiusi sotto intersezione?

Perché combinare due dipendenze neutre può richiedere contare simultaneamente due relazioni, oltre le capacità di una singola pila.

Dimostra la chiusura CF sotto concatenazione.

Nuovo simbolo iniziale S₀ con produzione S₀→S₁S₂, dove S₁ e S₂ sono gli iniziali delle grammatiche di L₁ e L₂.

Che cos’è una grammatica CF in forma ridotta?

Priva di ε-produzioni (eccetto forse S), produzioni unitarie e simboli inutili.

Qual è la relazione fra espressioni regolari, grammatiche regolari e ASF?

Sono modelli equivalenti: descrivono e riconoscono esattamente i linguaggi regolari.

Condizione di determinismo in un PDA.

Se δ(q, ε, Z) è definita allora δ(q, a, Z) non è definita per nessun a dell’alfabeto.

Perché XML è considerato ispirato ai linguaggi CF?

Perché la sua struttura gerarchica e annidata può essere descritta da grammatiche context-free e riconosciuta da PDA deterministici.

Qual è lo scopo principale del pumping lemma?

Mostrare che un linguaggio NON è regolare (o NON è context-free), non dimostrare che lo è.