Marco Pagnin, Page 4 Author

Un linguaggio finito è sempre regolare (senza loop).

Un linguaggio con loop è non regolare se contraddice il pumping lemma.

Un linguaggio con loop che rispetta il pumping lemma può essere o non essere regolare.

https://www.geeksforgeeks.org/theory-of-computation-pumping-lemma/

Il pumping lemma è una cavolata, espressa in una maniera complicata perché formale.

Ogni stringa sposta l'automa da uno stato all'altro, ma se ci sono più lettere che stati è ovvio che perché la stringa sia riconosciuta bisogna che ripeta più volte il passaggio attraverso alcuni stati.

Gli angolofoni lo chiamano principio dei buchi della piccionaia, noi principio dei cassetti, ma il senso non cambia.

In pratica quindi:

1. for each i ≥ 0, xyⁱz ∈ A significa che A contiene xz, xyz, xyyz, xyyyz, xyyyyz...
2. |y| > 0 significa, banalmente, che non posso scegliere ε come y, cioè devo avere un y che contiene qualcosa. Al limite, lo ripeto zero volte...
3. |xy| ≤ p significa che o p si ferma a x oppure è lungo almeno xy

Da questi tre punti si evince anche che:

1. x e z possono essere ε
2. se p > 0, allora o x o y devono essere diversi da ε

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.