Suggerimenti










Esercizio1

Utilizzare una categoria grammaticale distinta per ogni lettera: la categoria contiene tutte le parole del linguaggio che non hanno tale lettera come lettera iniziale Esercizio2 Utilizzare uno stato distinto per ogni lettera: lo stato e' attraversato allorche' la parola contenga tale lettera. Esercizio3 Utilizzare stati in grado di distinguere tra 0, dispari e pari, numero di "a" gia' riconosciute. Esercizio4 Vale il suggerimento di esercizio3 con l'avvertenza che gli stati finali e iniziali devono essere riesaminati Esercizio5 Si svolgano prima esercizio3 e/o esercizio4: Si osservi che il linguaggio richiesto l'intersezione dei linguaggi riconosciuti da tali automi. Allo scopo, si consideri l'esercizio8 Esercizio6 Esiste un modo sistematico per ottenere tali grammatiche: Si utilizza una particolare classe di grammatiche, note come lineari. Le produzioni di queste grammatiche hanno la forma: A::= c B, ovvero semplicemente A::= B, dove "A" e "B" sono nonterminali diversi e "c" e' un simbolo terminale (quindi dell'alfabeto Sigma). Purtroppo queste grammatiche non sono sempre regolari. La loro trasformazione in regolare puo' essere realizzata attraverso un procedimento sistematico basato sulla rimozione di ricorsione. Esercizio7 Ancora piu' semplice di esercizio4.
  Esercizio8a L'automa deve prevedere la presenza di tre stati in grado di discriminare tra nessuna occorrenza di "b", occorrenze di "b" in numero dispari, occorrenze di "b" in numero pari. La transizione dall'uno all'altro degli stati dipende unicamente da "b". Infine i soli primi due stati risulteranno stati finali mentre il primo anche, ed unico, stato iniziale. L'automa e' deterministico.
  Esercizio8b Una grammatica regolare per tale linguaggio puo' essere ottenuta osservando che il linguaggio e' unione di due linguaggi.


Esercizio13a

Lex e' uno strumento progettato per manipolare stringhe e individuare sottostringhe di esse che soddisfino vincoli esprimibili mediante espressioni regolari. Pertanto puo' essere utilizzato, come noi facciamo, per "studiare" grammatiche regolari ma non e' concepito per tale scopo e il suo uso non richiede specifiche competenze. Questa premessa e' obbligatoria per capire come talora possa accadere che soluzioni formalmente corrette, complete e efficenti non trovino piena esprimibilita' in Lex, o altrimenti risultino piu' inefficenti di soluzioni che dovrebbero avere costi maggiori, o infine scritture scorrette si rivelino in Lex soluzioni lecite e complete. Di fatto Lex nasconde alcuni meccanismi (quali la complementazione) non esprimibili nelle grammatiche regolari.
Pertanto daremo due soluzioni Lex.
La prima e' una grammatica regolare che costruisce le frasi del linguaggio osservando che:
  1.     possiamo ordinare il nostro alfabeto
  2.     data una qualunque parola w del linguaggio, sia "a" la lettera di valore minore che occorre nalla parola, ed n il numero di occorrenze di "a" in w. Allora,  w=w0.aw1. ... . awn, dove w0 e wn possono essere vuote, e w1,...,wn-1 sono parole del linguaggio non contenente "a".
  3.     Ad ogni lettera dell'alfabeto associamo il sottolinguaggio delle parole che contengono tale lettera e che sono strutturate come w sopra.
Notiamo che in questo modo ad ogni lettera possiamo far corrispondere una categoria grammaticale e tale categoria puo' essere espressa facendo ricorso alle categorie grammaticali di lettere di valore maggiore: concludiamo che le categorie grammaticali sono totalmente ordinabili e la gramatica e' quindi regolare.
La seconda soluzione si basa sull;uso del meccanismo di complementazione. A tale soluzione non corrisponde tuttavia, alcuna grammatica regolare.
[ Home | Back ]

 
  
Ultimo aggiornamento 7 Marzo 2002