Algoritmi e Principi dell'Informatica Alessio Massetti 15 Novembre 2011

(1)

Algoritmi e Principi dell'Informatica

Alessio Massetti 15 Novembre 2011

1 Linguaggi

1.1 Tipi di linguaggi

1.1.1 Linguaggio regolare

Un linguaggio si dice regolare se è riconoscibile da un automa a stati niti come automa a potenza minima

1.1.2 Linguaggio Context-Free

Un linguaggio si dice context-free se è riconoscibile da un automa a pila non deterministico come automa a potenza minima

1.1.3 Linguaggio Context-Sensitive

Un linguaggio si dice context-sensitive se è riconoscibile da una macchina di Turing a singolo nastro come automa a potenza minima

1.1.4 Linguaggio ricorsivamente numerabile

Un linguaggio si dice ricorsivamente numerabile se è riconoscibile da una macchina di Turing come automa a potenza minima

1.2 Cheat Sheet

• I simboli che appartengono all'alfabeto di input sono solitamente minuscoli

• s.t signica s concatenato t

• r | s signica r or s

• Le parentesi forzano una precedenza di lettura

• s^∗ signica un numero arbitrario di s

• s⁺ signica almeno una s. E' equivalente a s(s)^∗

2 Automi

2.1 FSA

Composto da freccia per stato iniziale e stati nali cerchiati. Deterministico se da ogni stato esce una sola freccia per ogni possibile input. Non vengono disegnati gli stati di errore. Può essere usato come riconoscitore di linguaggi

(4)

2.1.1 Riconoscitore di linguaggi

Essenzialmente la stringa di input va riconosciuta passando da stato a stato. Ricor- darsi sempre:

• Lo stato iniziale è stato denito ed è uno solo?

• Il linguaggio in input accetta la stringa vuota?

• L'FSA può leggere altri linguaggi oltre a quello dato? (il riconoscitore di linguaggi deve riconoscere solamente quello desiderato)

2.1.2 Negazione di FSA

Si invertono stati di accettazione e non accettazione. Vanno prima disegnati gli stati di errore (che sono stati di non accettazione) e invertiti

2.1.3 Intersezione di FSA

Si fa il prodotto cartesiano degli stati dei due automi. Lo stato iniziale è quello deteterminato dal prodotto cartesiano dei due stati iniziali.

Sono invece nali tutti quegli stati prodotto dei due stati nali. Partendo dallo stato iniziale si deriva quindi la funzione δ per ogni stato.

2.1.4 Unione di FSA

E' complicato realizzarla come l'intersezione e la negazione, ovvero agendo con un algoritmo proprio sull'automa.

Si realizza sfruttando de Morgan: a ∪ b = ¬ ((¬a) ∩ (¬b)) ovvero: due comple- menti, la loro intersezione e un altro complemento in serie.

2.1.5 Traduttore

Un automa può anche essere usato come traduttore quando produce un linguaggio di output. In questo caso si può associare una stringa di output per ogni stringa di input letta. Eventualmente anche la vuota.

2.1.6 Rimozione del non determinismo

Per rimuovere il nondeterminismo in un FSA si deve partire dallo stato iniziale q0 e spostarsi seguendo le frecce sull'automa non deterministico. Quando il nondeterminismo porta a divergere su più di uno stato si indica il risultante facendo il prodotto cartesiano degli stati. Quando si riparte da questi si guarda l'input tra i due stati a quale porta facendo anche di questi il prodotto cartesiano. Uno stato così ottenuto è nale se e solo se almeno uno di quelli di partenza è nale. Per vericare che sia corretto: ogni stato deve avere tutti i possibili input in entrata e in uscita.

(5)

2.2 PDA

A dierenza dell'FSA il PDA può contare le lettere. Questo porta a considerare nondeterministico solamente il PDA che fa la stessa transizione quando legge la stessa lettera dall'input e dalla pila o quando legge la stringa vuota.

2.2.1 Gestione della pila

L'automa legge la cima della pila. Una volta letta può decidere se buttarla via, rimetterla al suo posto o rimetterla al suo posto insieme ad un altro simbolo. Ad ogni transizione viene quindi tolto un simbolo dalla pila e rimessi facoltativamente in pila zero, uno o due simboli compreso quello letto.

2.2.2 Cosa può leggere

Tutti i linguaggi dove è necessario contare e tutti i linguaggi riconosciuti da un FSA.

Esempi di linguaggi:

• aⁿbⁿ

• I derivati del primo che compiano operazioni matematiche sul secondo: aⁿb²ⁿ; aⁿbⁿ²

• Qualsiasi linguaggio abbia in mezzo cose numerabili: waⁿwbⁿwcon w(a, ..., z)^∗ 2.2.3 Cosa non può leggere

Tutti i linguaggi dove è necessario contare più di una volta o separare il calcolo.

Alcuni esempi:

• Non è possibile leggere linguaggi che debbano contare più di due volte: aⁿbⁿcⁿ

• Non è possibile leggere linguaggi che debbano spezzare a metà uno dei due calcoli aⁿb^mc^lcon l = n + m. In quest'ultimo caso è infatti possibile creare un'automa che legga solo il linguaggio aⁿ(b + c)^m+l

2.2.4 Potenza minima

Non occorre nemmeno un PDA per leggere linguaggi che devono contare un numero

nito di cose, ad esempio: a⁴b⁵può essere riconosciuto da un FSA. In questo caso si parla di automa a potenza minima per riconoscere il linguaggio.

3 Macchina di Turing

3.1 Cosa legge

La Macchina di Turing riconosce tutti i linguaggi computabili.

(6)

3.2 Composizione

E' composta da un nastro di input, un nastro di output e uno o più nastri di memoria.

La macchina può muovere a destra a sinistra o restare ferma con la testina su ogni nastro. Tutte le macchine di Turing sono comunque equivalenti a una sola macchina di Turing con un nastro di memoria.

3.3 Funzionamento

Si usa un simbolo accessorio Z0 per indicare l'inizio del nastro. In caso non ci sia nulla sul nastro si indica con un blank. La gestione dei nastri avviene tramite un FSA

4 Reti di Petri

4.1 Cosa sono

Una rete di petri è un automa nondeterministico composto di stati e di transazioni.

Ogni transazione richiede un token in ognuno degli stati di partenza. Le transazioni vengono eseguite nondeterministicamente

4.2 Potenza di calcolo

Una rete di petri risolve tutti i problemi che è in grado di risolvere un FSA e alcuni problemi che è in grado di risolvere un PDA. La rete di Petri riesce infatti a contare più di una volta ma non riesce a ricordarsi cosa ha contato. Una RDP riconosce, ad esempio,aⁿbⁿcⁿ

4.3 Archi inibitori

Per ampliare la potenza delle RDP si possono usare gli archi inibitori, ovvero degli archi che fanno scattare la transazione collegata solamente se lo stato di partenza non contiene token. Una RDP di questo genere ha la stessa potenza di calcolo di una MT

5 Grammatiche

5.1 Cosa sono

Le grammatiche sono essenzialmente un altro formalismo per denire il linguaggio, descrivono come un linguaggio viene generato. Sono composte da un assioma, delle regole di derivazione e dei caratteri terminali e nonterminali. Per convenzione i caratteri nonterminali si scrivono con la lettera maiuscola, l'assioma viene chiamato S

(7)

5.2 Equivalenze

5.2.1 Linguaggi regolari

Una grammatica riconosce un linguaggio regolare se ha come regole di derivazione solamente A → aB | B | ε, dove A e B sono due diversi qualsiasi caratteri nonterminali. Una grammatica di questo tipo è detta di tipo 3.

5.2.2 Linguaggio Context-Free

Una grammatica riconosce un linguaggio context-free se ha come regole di derivazione oltre a quelle dei linguaggi regolari almeno una regola A → ABC dove A, B, C sono tre diversi qualsiasi caratteri nonterminali. Una grammatica di questo tipo è detta di tipo 2.

5.2.3 Linguaggio Context-Sensitive

Una grammatica riconosce un linguaggio context-sensitive se ha come regole di derivazione oltre a quelle dei linguaggi context free almeno una regola α → β con|α| ≤ |β| dove α e β sono un insieme qualsiasi di caratteri terminali nonterminali mischiati a piacere (in una maniera ovviamente non compresa nei linguaggi regolari e context free, esempio: ABC → aBCc. Una grammatica di questo tipo è detta di tipo 1.

5.2.4 Linguaggio ricorsivamente numerabile

Una grammatica riconosce un linguaggio context-sensitive se ha come regole di derivazione oltre a quelle dei linguaggi context free almeno una regola α → β dove α e β sono un insieme qualsiasi di caratteri terminali nonterminali mischiati a piacere (in una maniera ovviamente non compresa nei linguaggi regolari e context free, esempio: ABC → aB. Una grammatica di questo tipo è detta di tipo 0.

5.3 Tecniche di costruzione

5.3.1 Coppia ordinata

Per costruire una coppia ordinata si usa la tecnica dei linguaggi ben parentesizzati.

Esempio: aⁿbⁿ S → aAb A → aAb| ε

5.3.2 Più di una coppia ordinata

Analogamente al punto precedente proviamo a costruire aⁿc^md^mbⁿ. In questo esempio costruisco prima le coppie di nonterminali, li permuto e successivamente li trasformo in terminali.

S → XS | S → SY

(8)

Y → Y CD DC → CD BA → AB BC → CB BD → DB A → a B → b C → c D → d

5.3.3 Palindromi

E' possibile dimostrare che se un linguaggio è palindromo allora esiste una grammatica che lo genera.

Algoritmi e Principi dell'Informatica Alessio Massetti 15 Novembre 2011