Soluzioni Proposte
Una grammatica regolare per il
linguaggio L contenente tutte le parole non vuote formabili sull'alfabeto
∑={a,b,c,d,...,z} tali che mai occorrono due simboli consecutivi uguali
SOLUZIONE
Utiliziamo una categoria grammaticale
Ca distinta per ogni distinta lettera "a" dell'alfabeto.
La categoria definisce (ha come linguaggio associato) l'insieme di tutte le
parole del linguaggio L che non hanno tale lettera come lettera iniziale, inclusa
la parola vuota. La grammatica richiesta e' quindi G = <N È {S},
∑, S, P>, per insieme di non terminali N, categoria iniziale e insieme di
produzioni tali che:
· Definizione di N: " a Î S, $ Ca Î N
· Definizione di P:
o "
a Î
S,
S::= a Ca Î P
o " Ca Î N
§ Ca::= e Î P
§ Ca::= b Cb Î P, " b ≠ a Î S,
La soluzione e' completa e parametrica rispetto a ∑. Ad esempio, sia ∑=
{a,b,c}. La grammatica prodotta ha le seguenti produzioni:
|
S ::= a Ca | b Cb | c Cc |
|
Ca ::= b Cb | c Cc | e |
|
Cb ::= a Ca | c Cc | e |
|
Cc ::= a Ca | b Cb | e |
Notiamo tuttavia, che tale soluzione non risponde completamente a quanto richiesto, in particolare non definisce una grammatica regolare. Per ottenere una tale grammatica possiamo seguire due approcci diversi:
· A) Osserviamo che la grammatica e' lineare, quindi procediamo in accordo al procedimento di esercizio 6.a
· B) Riflettiamo su un altro modo di generare il linguaggio, la nuova formulazione non deve mai fare ricorso a definizioni induttive.
Soluzione B
Dobbiamo riformulare la grammatica senza fare ricorso a definizioni induttive.
In effetti il “pumping” lemma o lemma di iterazione dei linguaggi regolari ci
dice che ogni stringa a di lunghezza maggiore di un opportuno e fissato n è sempre ottenibile da una composizione . Quindi
anche le stringhe di L devono poter essere ottenute mediante scomposizioni di
tale forma. Confrontate la vostra soluzione con quella proposta per l'esercizio
13.a.
Utiliziamo uno stato distinto per ogni distinta lettera dell'alfabeto. Tale stato e' attraversato allorche' la parola contenga tale lettera. L'automa richiesto e' quindi A = <N U {0}, Sigma, Move, {0}, N>, per insieme di stati N, stato iniziale 0 e funzione Move cosi' definita (utiliziamo una iniettiva i:Sigma -> [1..#Sigma], dove # e' la cardinalita'):
· per ogni a ISIN Sigma,
Move(0,a) = i(a)
· per ogni a ISIN Sigma, per ogni b=/=a ISIN Sigma,
Move(i(a),b) = i(b)
La soluzione e' completa e parametrica rispetto a Sigma. La si applichi, ad
esempio, per Sigma = {a,b,c}.
Utiliziamo
stati in grado di distinguere tra pari e dispari numero di "a" gia'
riconosciute. In particolare:
0:
attraversato fintantoche nessun "a" sia stato riconosciuto oppure una
nuova "a" appena riconosciuta conduca a un numero pari di occorrenze
totali di "a" nella parola finora scandita.
1:
attraversato allorche una nuova "a" appena riconosciuta conduca a un
numero dispari di occorrenze totali di "a" al momento riconosciute.
A = <{0,1}, {a,b,c}, Move, {0}, {0}>
dove
Move e' descritta dalla seguente tabella:
|
|
a |
b |
c |
|
0 |
1 |
0 |
0 |
|
1 |
0 |
1 |
1 |
Utiliziamo stati in grado di distinguere tra pari e dispari numero di "a", indichiamo 2(a) e 1(a), e pari e dispari numero di "b", indichiamo 0(b), 1(b), 2(b). Notiamo una certa asimmetria: per le motivazioni si risova prima l'esercizio4. I nostri stati saranno i seguenti: a fianco e' indicato quando lo stato sara' attraversato
0: 2(a)0(b)
1: 1(a)0(b)
2: 1(a)1(b)
3: 1(a)2(b)
4: 2(a)1(b)
5: 2(a)2(b)
A = <{0,1,2,3,4,5}, {a,b,c}, Move, {0}, {0,4}>
dove Move e' descritta dalla seguente tabella:
|
|
a |
b |
c |
|
0 |
1 |
4 |
0 |
|
1 |
0 |
2 |
1 |
|
2 |
4 |
3 |
2 |
|
3 |
5 |
2 |
3 |
|
4 |
2 |
5 |
4 |
|
5 |
3 |
4 |
5 |
Associamo ad ogni stato "i"
dell'automa il non terminale "Si" ed introduciamo le seguenti
produzioni (si noti la produzione Si::=e allorche'
i sia stato finale):
|
S0 ::= a S1 | b S0 | c S0 | e |
|
S1 ::= a S0 | b S1 | c S1 |
Otteniamo
una grammatica non regolare che riscriviamo in:
|
S0 ::= a S1 | (b | c) S0 | e |
|
S1 ::= a S0 | (b | c) S1 |
e
trasformiamo, risolvendo la ricorsione mediante interpretazione delle
produzioni come equazioni sugli insiemi definiti dai linguaggi L(S0) e L(S1),
in una regolare equivalente:
1.
riduzione
ricorsione da S0
|
S0 ::= (b | c)* (a S1 | e) |
|
S1 ::= a S0 | (b | c) S1 |
§ rimpiazzamento
|
S0 ::= (b | c)* (a S1 | e) |
|
S1 ::= a (b | c)* (a S1 | e) | (b | c) S1 |
§ riduzione ricorsione da (commutativita' e
associativita'): S1 ::= (a (b | c)*a | b | c)
S1 | a (b | c)*
|
S0 ::= (b | c)* (a S1 | e) |
|
S1 ::= (a (b | c)*a | b | c)* a (b | c)* |
La grammatica puo' essere facilmente espressa dall'unione di due linguaggi:
A
ciascun linguaggio associamo una categoria lessicale e un'espressione regolare
che lo esprima:
|
S::= N | D |
|
N::= (a | c)* |
|
D::= P b N |
|
P::= (N b N b)* |
Notare
l'introduzione della categoria lessicale P, categoria ausiliaria che definisce
il linguaggio delle occorrenze pari di "b" se occorre.
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:
· possiamo ordinare il nostro alfabeto
· 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".
· 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.
Esercizio 15 (Espressioni
regolari: estensioni)
a)
prodotto (giustapposto): L1 x L2 = {u.v | u Î L1, v Î L2}
è linguaggio regolare;
b)
unione: L1 È L2 è linguaggio regolare;
c)
complemento: L = {u | u Î S*-L} è
linguaggio regolare;
d)
intersezione: L1 Ç L2 è linguaggio regolare;
assunti L, L1, L2 linguaggi regolari su S.
Per i casi a) e b) è immediato, dati automi per L1 ed L2, ottenere automi
per L1xL2 ed L1 È L2. Si dia un procedimento per ottenere un automa nei casi
c) e d). Ovvero si risolvano i seguenti esercizi:
1)
Sia A un automa per il linguaggio regolare L, si dia un
procedimento per generare un automa A per il linguaggio L,
complemento di L su S.
2) Siano
A1 ed A2 automi per, rispettivamente, il linguaggio regolare L1 e il linguaggio
regolare L2, si dia un procedimento per generare un automa A1ÇA2
per il linguaggio regolare L1 Ç L2, intersezione dei linguaggi
L1 ed L2.
3) Come
sappiamo, le espressioni regolari hanno la stessa potenza degli automi a stati
finiti, ovvero descrivono la stessa classe di linguaggi descritta dagli automi
a stati finiti, cioè la classe dei linguaggi regolari. La usuale definizione di
espressione regolare prevede i soli operatori di giustapposizione “.”, altenato
“|”, potenza finita, “_k”, potenza limite o stella di Kleene, “_*”. Esistono però definizioni, come quelle
adottate nei sistemi LEX o in linguaggi come PERL, che includono anche operatori
di negazione “~”, e di congiunzione “&”. Queste definizioni introducono una
classe di espressioni più potente di quella usuale?
SOLUZIONE
|
Ultimo aggiornamento 7
Marzo 2203 |