Calcolabilità e linguaggi formali, Page 3 Categoria

a. Theorem

Show that if M is a DFA that recognizes language B, swapping the accept and nonaccept states in M yields a new DFA recognizing the complement of B. Conclude that the class of regular languages is closed under complement.

a. Proof

This proof is based on induction.

Base case: a DFA with a single state, don't care what is the alphabet. Every letter brings to the only state. Obviously, if the state is an accepted state (F = {q₀}), the DFA accepts every string; if the state is a non-accepted state (F = ∅), the DFA doesn't accept strings.

Inductive step: Let N a DFA that respect the theorem. If we add a new state F_new, we must add an outgoing arrow for each letter and we can add some incoming arrow, moving them from other states.

Now, there are three cases: if the string ends before reaching F_new, the theorem is proven, because the existence of F_new isn't relevant. If the string ends at F_new, the change of the acceptance of F_new inverts the behavior of the DFA.

If the string ends at the state after F_new, that we can name F_new+1, the change of the acceptance of F_new+1 inverts the behavior of the DFA.

After F_new+1, we are again inside N, so the theorem is proved.

a. Proof (2)

For each string s, the membership of each state at F don't change the path that s follows. So, if s ends in an accepted state, the string is accepted, and changing this state the string isn't accepted anymore; and vice versa.

a. Conclusion

Let S a class of strings s composed by letters of Σ. Each string of s must belong to a regular language recognized by N or ¬N, since every state is accepted in N or ¬N.

Since "A language is called regular language if some finite automaton recognizes it" (Sipser, definition 1.16), all the languages that recognize every string s must be recognized by N or ¬N.

b. Theorem

Show by giving an example that if M is an NFA that recognizes language C, swapping the accept and nonaccept states in M doesn’t necessarily yield a new NFA that recognizes the complement of C. Is the class of languages recognized by NFAs closed under complement? Explain your answer.

b. Proof

A simple example is:

N = ({q₀, q₁}, {A, B}, δ, q₀, {q₀, q₁})
δ = (q₀, A) = q₁

the string "B" is not recognized both by N and ¬N

Since every NFA have an equivalent DFA (Sipser, theorem 1.39), and the NFA is a special class of DFAs, the class of NFA is closed under complement.

Il capitolo 4 è tutto basato sulla dimostrazione che quanto visto nei capitoli precedenti è decidibile (o no).

A_DFA è decidibile: si crea una macchina di Turing che, dati (B, w) con B automa e w stringa, simuli il DFA. Se la simulazione finisce in uno stato accettato, accetta, altrimenti rifiuta.

A_NFA è decidibile: si potrebbe procedere come per la DFA e creare una TM che simuli il NFA, ma c'è un'altra strada: convertire il NFA in un DFA, e poi procedere come per il punto precedente.

A_REX è decidibile: si converte l'espressione regolare in una NFA e si procede con il punto precedente.

La discussione che segue è informale, e serve a dare indicazioni su cosa sono e come si comportano le macchine di Turing.

Una macchina di Turing è composta, come un DFA, da un insieme di stati e da una sequenza di input i cui "caratteri" sono quelli previsti da un alfabeto.

Anche le macchine di Turing hanno uno stato iniziale, ma in più - rispetto a una DFA - hanno anche un "nastro" su cui possono essere memorizzate delle informazioni.

Siccome le TM devono essere più semplici possibile, anche il nastro ha un funzionamento estremamente semplice: è una striscia discreta (cioè si passa da 1 a 2, da 2 a 3 eccetera, senza posizioni intermedie come 1/2) che può memorizzare un carattere per cella da un insieme di caratteri predefiniti. La TM ha una testina che legge e scrive un carattere alla volta e si può spostare a destra o a sinistra di una sola posizione alla volta.

I caratteri di input sono un sottoinsieme dei caratteri possibili nel nastro (in teoria possono anche coincidere, ma nella pratica servono caratteri aggiuntivi nel nastro).

Anche il passaggio da uno stato all'altro è discreto, come, in un calcolatore moderno, un clock fa passare una CPU da uno stato all'altro in maniera virtualmente discreta.

Il nastro è illimitato, ha una fine a sinistra e solitamente è marcato da un ˽ (blank) a destra.

Per quanto riguarda l'insieme di funzioni δ che cambiano di stato la TM, δ prende in ingresso lo stato corrente e il carattere del nastro (lettura) e fa questo:

1. cambia di stato la TM
2. scrive un carattere sul nastro nella posizione corrente
3. si sposta a destra o a sinistra

Formalmente, si scrive δ(q_i, b) = (q_j, c, R), dove q_i e q_j sono stati della TM, b, c sono caratteri del nastro e L|R indica se la testina si sposta a destra o a sinistra.

Una TM può terminare la sua elaborazione in uno stato considerato accepted o in uno stato considerato rejected, e con questi due abbiamo completato tutto ciò che serve per definire completamente una TM.

In aggiunta, una TM può non terminare mai (per esempio se diciamo di andare avanti e indietro sulla stessa posizione all'infinito). Salvo casi banali, decidere se una macchina sta ancora lavorando ma arriverà a q_accepted o q_rejected oppure se lavorerà all'infinito senza arrivare mai a uno stato finale è un problema importante.

Limitare a sinistra

Mentre a destra la macchina può scorrere il nastro all'infinito e marcare la fine (provvisoria) del nastro con un carattere di terminazione ˽, a sinistra si ferma una volta arrivato alla posizione iniziale. Siccome vogliamo che la macchina sia più semplice possibile, anche a discapito della quantità di lavoro che deve fare, per capire quando arriva a sinistra può scrivere un carattere speciale nella posizione corrente e tentare di andare a sinistra: se ci riesce, torna indietro, ripristina il carattere originale e poi di nuovo a sinistra; se invece trova di nuovo il carattere speciale significa che il tentativo di andare a sinistra è stato bloccato dal limite della TM e quindi in effetti è all'inizio del nastro.

Macchina multi nastro

Se immaginiamo una macchina di Turing con più di un nastro, sembra che questa sia più "potente" di una TM con un nastro solo, ma non è così: per rendere une TM multinastro equivalente a una TM a nastro singolo, è sufficiente creare una TM con un simbolo in più per delimitare la fine di ogni "nastro virtuale" e raddoppiare ciascun alfabeto per introdurre un insieme di simboli che rappresentano il posto in cui si trova la testina.

Da un punto di vista "alto livello", tra un delimitatore e l'altro si troveranno una serie di simboli appartenenti al "multinastro" originale, in più uno dei caratteri avrà un "pallino" sopra. Solo un carattere, nella sequenza delimitata, avrà il pallino, perché indica la posizione della testina, che è una sola.

La TM che otterremo sarà molto più articolata e macchinosa dell'originale, ma dal punto di vista potenziale è perfettamente equivalente.

Macchina nondeterministica

Per far funzionare una TM nondeterministica, è necessario creare un branch per ciascuna delle possibili configurazioni, ma il problema è che se entriamo in uno dei rami con una modalità depth-first rischiamo di ritrovarci in un loop di sotto-branch infinito, mancando di rilevare qualche ramo che potrebbe essere finito.

Allora la strategia migliore è breadth first (visita in ampiezza).

Creando una TM con tre nastri, uno di input, uno di simulazione e uno di indirizzi, che indica quale simulazione stiamo valutando, otterremo una TM deterministica equivalente alla TM nondeterministica (come sempre, più elaborata, ma equivalente).

Siccome abbiamo dimostrato in precedenza che una TM multinastro è equivalente a una TM mononastro, per transitività anche una TM nondeterministica è equivalente a una TM monostrato deterministica.

Enumeratore

Un enumeratore è una macchina di Turing con una stampante collegata.

è equivalente a una macchina di Turing.

Un pushdown automata è descritto come un insieme di stati Q, un alfabeto di input Σ, un alfabeto di stack Γ, un insieme di funzioni δ QxΣ_εxΓ_ε → QxΓ_ε, uno stato di partenza e un insieme di stati accettati. All'inizio lo stato è quello iniziale q₀ e lo stack è vuoto.

Nei diagrammi gli stati sono rappresentati dai "soliti" pallini con gli identificativi di stato q_qualcosa, mentre le frecce sono etichettate con σ, γ₁ → γ₂, dove γ₁ e γ₂ sono elementi dell'alfabeto dello stack Γ. Questo va interpretato come: se l'input è σ, allora leggo γ₁ e scrivo γ₂. Formalmente γ₁ e γ₂ sono sempre presenti, ma se il valore è ε allora effettuo il passaggio senza leggere o scrivere niente.

Quando devo dimostrare che un linguaggio riconosciuto da un pushdown automata è equivalente a un linguaggio context-free, inizio dicendo che se un linguaggio è context-free allora un pushdown automata lo riconosce.

Un CLF funziona sostituendo di volta in volta stringhe con altre stringhe più grandi, quindi il problma principale sta nel memorizzare questa stringa in un PDA. Per fare questo, si scrive la stringa nello stack. Ma lo stack può leggere o scrivere solo un carattere alla volta.

La funzione di transizione ha la caratteristica di essere nella forma δ(q, a, x) = (r, y), dove:

• q è lo stato attuale
• a è il carattere di Σ di input
• x è il carattere di Γ letto dalla pila
• r è lo stato di destinazione
• y è il carattere di Γ scritto nella pila

La funzione di transizione deve essere una tra le seguenti:

• δ(q, a, x)
• δ(q, ε, x)
• δ(q, a, ε)
• δ(q, ε, ε)

in altre parole, lo stato di partenza è - ovviamente - necessario, ma non è necessario che ci siano né un carattere di input (come negli NFA) né un carattere di stack.

 

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

Teorema	Codice (Sipser)	Pagina (Sipser)	Link alla dimostrazione (Italiano)
La classe di linguaggi regolari è chiuso per l'operazione di unione	1.25	45
La classe di linguaggi regolari è chiuso per l'operazione di concatenazione	1.26	47
Ogni automa finito nondeterministico ha un automa finito deterministico corrispondente	1.39	55
(Corollario) Un linguaggio è regolare se e solo se qualche automa finito nondeterministico lo riconosce	1.40	56
La classe dei linguaggi regolari è chiusa per l'operazione di unione	1.45	59
La classe dei linguaggi regolari è chiusa per l'operazione di concatenazione	1.47	60
La classe dei linguaggi regolari è chiusa per l'operazione di star	1.49	62
Un linguaggio è regolare se e solo se qualche espressione regolare lo descrive	1.54	66
(Lemma) Se un linguaggio è regolare, allora è descritto da un'espressione regolare	1.60	69
Pumping lemma: se A è un linguaggio regolare, allora c'è un numero p (la lunghezza "pump") per cui, se s è una stringa in A di lunghezza come minimo p, allora s può essere divisa in tre pezzi, s = xyz, che soddisfano le seguenti condizioni: ∀ i ≥ 0, xyiz ∈ A |y| > 0 |xy| ≤ p	1.70	78
Ogni linguaggio senza contesto è generato da una grammatica senza contesto in una forma normale di Chomsky	2.9	107
Un linguaggio è senza contesto se qualche automa pushdown lo riconosce	2.20	115
(Lemma) Se un automa pushdown riconosce qualche linguaggio, allora è senza contesto	2.27	119
(Claim) Se Apq genera x, allora x può portare P da p con stack vuoto a q con stack vuoto	2.30	121
(Claim) Se x può portare P da p con stack vuoto a q con stack vuoto, Apq genera x	2.31	121
Pumping lemma per linguaggi senza contesto: se A è un linguaggio senza contesto, allora c'è un numero p (la lunghezza "pump") per cui, se s è una stringa in A di lunghezza come minimo p, allora s può essere divisa in cinque pezzi, s = uvxyz, che soddisfano le seguenti condizioni: ∀ i ≥ 0, uvixyiz ∈ A |vy| > 0 |vxy| ≤ p	2.34	123
Ogni macchina di Turing multinastro ha un'equivalente macchina di Turing a singolo nastro	3.13	149
(Corollario) Un linguaggio è Turing-riconoscibile se e solo se qualche macchina multinastro di Turing lo riconosce	3.15	150
(Corollario) Un linguaggio è Turing-riconoscibile se e solo se qualche macchina di Turing nondeterministica lo riconosce	3.18	152
(Corollario) Un linguaggio è decidibile se e solo se qualche macchina nondeterministica di Turing lo decide	3.19	152
Un linguaggio è Turing-riconoscibile se e solo se qualche enumeratore lo enumera	3.21	153
ADFA è un linguaggio decidibile	4.1	166
ANFA è un linguaggio decidibile	4.2	167
AREX è un linguaggio decidibile	4.3	168
EDFA è un linguaggio decidibile	4.4	168
EQDFA è un linguaggio decidibile	4.5	169
ACFG è un linguaggio decidibile	4.7	170
ECFG è un linguaggio decidibile	4.8	171
Ogni linguaggio senza contesto è decidibile	4.9	172
ATM è indecidibile	4.11	174
R è incontabile	4.17	177
(Corollario) Alcuni linguaggi non sono Turing-riconoscibili	4.18	178
Un linguiaggio è decidibile se e solo se è Turing-riconoscibile e co-Turing-riconoscibile	4.22	181
(Corollario) ATM non è Turing-riconoscibile	4.23	182
HALTTM è indecidibile	5.1	188
ETM è indecidibile	5.2	189
REGULARTM è indecidibile	5.3	191
EQTM è indecidibile	5.4	192
(Lemma) Sia M un LBA con q stati e g simboli nell'alfabeto del nastro. Ci sono esattamente qngn distinte configurazioni di M per un nastro di lunghezza n	5.8	194
ALBA è decidibile	5.9	194

 

Un automa finito nondeterministico generalizzato è un NFA con delle espressioni regolari al posto dei semplici membri dell'alfabeto Σ.

Si usa, per prassi:

• Lo stato iniziale ha frecce uscenti verso tutti gli altri stati, ma non ha frecce entranti;
• C'è un solo stato di accettazione, ha solo frecce entranti da ogni altro stato e non ha frecce uscenti. Inoltre non coincide con lo stato iniziale;
• A parte gli stati iniziale e finale, ogni stato ha una freccia che va verso ciascuno degli altri stati e una verso se stesso.

La definizione formale di GNFA è

Symbol	Meaning
Q	finite set called the States
Σ	finite state called Alphabet
δ:(Q-{qaccept})x(Q-{qstart})→R	transition function (tutte le combinazioni possibili, tranne quelle che partono dallo stato accettato e finiscono nello stato di partenza)
qstart∈Q	start state
qaccept	accepted states

La conversione di una GNFA in una DFA consiste in un semplice algoritmo:
CONVERT(G)

• sia k il numero di stati di G
• se k = 2 allora G deve essere uno stato di start, uno stato di accept e una sola freccia contenente un'espressione regolare
• se invece k > 2, allora si calcola Q' = Q - q_rip, cioè per ogni stato diverso da start e accept, si convertono le frecce in un equivalente senza lo stato rip:
  δ'(q_i, q_j) = (R1)(R2)*(R3)∪(R4), dove:
• • R1 = δ(q_i, q_rip)
  • R2 = δ(q_rip, q_rip)
  • R3 = δ(q_rip, q_j)
  • R4 = δ(q_i, q_j)
• si applica CONVERT a G'

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

Per chi viene dal mondo dei database è facile capire la differenza - sottile - tra ε e ∅: la prima rappresenta un insieme contenente una sola stringa vuota (SET @var = ''), mentre il secondo rappresenta un insieme vuoto (SET @var = NULL).

L'insieme degli stati possibili in una DFA è l'insieme delle combinazioni degli stati di una NFA, incluso insieme vuoto.

Per esempio, con un insieme di stati di una NFA {1, 2, 3}, si ottiene un insieme di stati DFA {∅, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}

A questo punto compilo la tabella stati / alfabeto in base alle specifiche di NFA.