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 concatenamento1 2 1 2

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

Attenzione: { | = > 0 } 2 22 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 finale3

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