Linguaggi di programmazione - Spiegazione argomenti principali

APPUNTI DI LINGUAGGI DI PROGRAMMAZIONE

Indice

ERRORI TIPICI

Pag. 02, Cosa significa dimostrare che un linguaggio non è libero da contesto (tipo 2)

Pag. 02, a+b nelle Espressioni Regolari (Inteso come OR)

Pag. 02, (a+b)* nelle Espressioni Regolari (Inteso come ∑*)

cosa significa

Pag. 02,

Pag. 02, cosa significa e qual è il complemento di

Pag. 03, L*

2

Pag. 03,

Pag. 03, Grammatiche Lineari Destre – Precisazioni

Pag. 04, Stati Finali Automa; Stato Pozza Automa [Serve per fare il complemento]; Complemento Automa

CONCETTI AVANZATI

Pag. 06, Pumping Lemma CF – caso con 3 terminali – guida commentata passo passo

Pag. 09, Pumping Lemma CF – caso con 2 terminali – guida commentata passo passo

Pag. 10, Conversione di un Automa NDA --> DFA (ovvero da Non Deterministico a Deterministico)

Pag. 12, Proprietà di Chiusura (Tabella Semeraro)

Pag. 13, Unione e concatenazione grammatiche di tipo 2 (Libere da Contesto)

Pag. 13, Grammatiche tipo 2 particolari – (GNF [Greibach Normal Form], NLR, CNF)

Pag. 14, Intersezione Linguaggi tipo 3 / Intersezione Automi [Leggi di De Morgan]

Pag. 14, Unione grammatiche di tipo 3 (lineari destre) ℇ-produzioni)

Pag. 14, Automa -> Grammatica tipo 3 (come impostare le

Pag. 15, Unione Linguaggi di tipo 3 (unendo automi)

Pag. 15, Unione Automi (tramite Unione Grammatiche tipo 3)

[Nei casi particolari in cui non posso unirli a occhio, perché un automa itera su q0 o qualcosa torna indietro su q0, o casi simili]

Pag. 16-17, Esercizio svolto su Unione Automi tramite Grammatiche

Automa numeri Divisibili (o Non divisibili) Per n + Esercizio Svolto

Pag. 18,

Pag. 21, Da Automa a Espressione Regolare – Metodo 1: (R* + SU*T)* SU*

[È il metodo che mette Fanizzi nelle slide, personalmente non mi ci sono trovato bene, io uso il secondo ]

Pag. 23, Da Automa a Espressione Regolare – Metodo 2 (Usato dal software JFLAP)

[alternativo a (R* + SU*T)* SU*]

Pag. 26, Metodi per Abbreviare le Espressioni Regolari (Accorpare casi simili con Epsilon)

DIMOSTRARE CHE UN LINGUAGGIO NON È LIBERO DA CONTESTO (Tipo 2)

Quando un esercizio chiede di dimostrare che un linguaggio non è libero da contesto, devo applicare il pumping

lemma per i linguaggi liberi da contesto, e dimostrare che viene violato e quindi il linguaggio non è libero.

NON devo usare il pumping lemma per i linguaggi lineari destri (tipo 3) e dimostrare che viene rispettato per dire che

è di tipo 2, potrebbe anche non esserlo, potrebbe essere 1 o 0.

a+b NELLE ESPRESSIONI REGOLARI (INTESO COME OR)

∗

(

= + ) ∗ ∗

{, {}

() = ( + ) ∙ () ∙ () = } ∙ ∙ {}

Il + NON significa concatenazione. Il + significa OR.

∗ ∗

{

() = } { } , NON è { a b a* b), quella è la concatenazione:

⋃

OVVERO:

cioè, il linguaggio contiene stringhe che iniziano o per a oppure per b, e poi finiscono con a* b

(a+b)* NELLE ESPRESSIONI REGOLARI (INTESO COME ∑*)

∗ ∗ ∗ ∗ ∗ ∗

→ {, {}

= ( + ) () = ( + ) ∙ () ∙ () = } ∙ ∙ {}

OVVERO: (è un automa non deterministico, va convertito, spiego più avanti come)

cosa significa

è la stringa riflessa di w. Se w è 011, è 110.

cosa significa, e qual è il complemento di

∗

{ | {0,1}

= ∈ }

significa w concatenato . Se w è 011, e è 110, è 011110

Il complemento è l’ insieme di tutte le possibili stringhe su {0,1}*, ovvero tutte le possibili stringhe binarie, tranne

quelle del tipo (quindi tranne le palindrome). O meglio, dato che, pari o dispari che sia la lunghezza di w, dato

che ha la stessa lunghezza di w, le stringhe del tipo avranno lunghezza doppia rispetto a w, per cui per forza

pari (poiché la somma di due numeri pari è pari, e la somma di due numeri dispari è pari) . Quindi il complemento

sono le stringhe binarie di lunghezza dispari (come 010010010) + le stringhe che non sono palindrome.

Spesso ho sentito dire “il complemento è il riflesso / l’inverso / l’ opposto, l’ inverso di una palindroma è la

palindroma stessa, quindi il complemento di è sempre “

L* (Iterazione di un Linguaggio)

Le infinite combinazioni di parole (inclusa la stringa vuota) ottenibili combinando le parole di L

Esempio: ∑ = {a, b} L = {aba, bb}

∑* = { ε, a, aa, aaa, […], b, bb, bbb, […], ab, abb, […], ba, baa, […], ababaa, […], babbaaaabaab, […] }

L* = { ε, aba, abaaba, […], bb, bbbb, […], ababb, ababbbb, […], bbaba, bbabaaba, […] }

QUINDI

∈

aab ∑*

∉

aab L*

(Potenza di un Linguaggio)

2 { |

= ⋅ = ∈ , ∈ } , è un caso speciale di concatenamento

1 2 1 2

Si prendono due parole qualsiasi, anche diverse fra loro, non è la stessa parola ripetuta due volte

ATTENZIONE:

{ |

= > 0 } 2 2

2 2 2 2 2 2

{ ( ) | { |

> 0 } è > 0 } , è { | > 0 }

NON è ,

2

{ |

è > 0, > 0 } ,

la prima sequenza di a, b, può avere lunghezza diversa dalla seconda, non è l’ insieme di concatenazioni della stessa parola

ripetuta due volte

GRAMMATICHE LINEARI DESTRE (TIPO 3) – PRECISAZIONI

Due sole forme di produzione accettate:

→

1) , con b ≠ stringa vuota

→

2) , con b che può essere stringa vuota ε

OVVERO

1) L’ NT produce uno e un solo terminale (diverso da stringa vuota), seguito da uno e un solo NT a destra

(da ciò il nome della grammatica, perché essendo sempre a destra l’ NT, la stringa cresce verso destra, e producendo ogni NT un

solo terminale, cresce in maniera lineare)

2) L’ NT produce uno e un solo terminale (in tal caso può anche essere stringa vuota)

QUINDI

→ NON è lineare destra (produce due terminali)

→ NON è lineare destra (non produce nessun terminale)

→ NON è lineare destra (produce due NT)

→ NON è lineare destra (il NT è a sinistra)

→ NON è lineare destra (produce due terminali)

STATI FINALI AUTOMA

Uno stato è finale quando posso arrivarci solo con una o più parole valide.

NON devo poter arrivare in uno stato finale con parole ancora in costruzione, né con parole non ammesse dal

linguaggio.

Se il linguaggio contiene la parola vuota, è anche uno stato finale oltre che iniziale.

0

Gli stati finali si denotano sul diagramma dell’ automa con due cerchi concentrici.

STATO POZZA DI UN AUTOMA [Serve per fare il complemento di un automa]

Def. Uno stato da cui non è possibile raggiungere nessuno stato finale.

È uno stato opzionale (che posso disegnare per completezza o per usare alcuni algoritmi che lo richiedono, oppure

posso trovarne già presenti in automi fornitimi come esercizio)

Esempio 1:

Una volta entrato in non è più possibile raggiungere uno stato finale

3

Esempio 2:

L’ automa M:

Ha come tabella delle transizioni

È un automa parziale. Posso completarlo aggiungendolo uno stato pozza (opzionale):

1) Collego tutti gli stati con produzioni mancanti allo stato pozza

2) (DA NON DIMENTICARE) Itero lo stato pozza su se stesso.

COMPLEMENTO DI UN AUTOMA

1.1) Disegno lo stato pozza (ovvero completo la tabella delle transizioni, rendendo completo l’ automa)

1.2) Non devo dimenticarmi di fare iterare lo stato pozza su se stesso per tutti i simboli dell’ alfabeto dell’ automa

2) Inverto F: gli stati finali diventano non finali, gli stati non finali diventano finali (anche lo stato pozza diventa finale)

ESERCIZIO SUL COMPLEMENTO DI UN AUTOMA

Dato R = (00)* (11)* 1, Trovare M tale che T(M) = S(R), e trovare il complemento di M

S(R) = {00}* unione {11}* unione {1},

S(R) = { α β 1 | α = (00)* , β = (11)* }

ovver