Linguaggi e traduttori, esercizi espressioni regolari.
Salve ragazzi ho una domanda semplice semplice.
Se si vuol dimostrare che una espressione regolare $r$ definisce un certo linguaggio $L$ si procede in 2 passi? Come per la grammatiche intendo...ovvero.
1. Tutte le stringhe di $L$ sono catturate da $r$
2. $r$ cattura solo stringhe di $L$
Per le grammatiche invece si procede, in generale
1. $G$ genera stringhe di $L$
2. Tutte le stringhe di $L$ sono generate da $G$
Nel caso delle espressioni regolari in particolare se per esempio prendo la seguente
$r = a ( a | b )^* a$
questa espressione cattura, e si vede ad occhio, tutte le stringhe definite sull'alfabeto $\Sigma = { a , b }$ che iniziano e finiscono per $a$
Per dimostrare però che è vero ciò che dico considero
1. Tutte le stringhe di $L$ sono catturate da $r$
La generica stringa di $L$ è una stringa del tipo $a \omega a$ questa stringa la possiamo vedere come concatenazione di tre stringhe
$s_1 = s_3 = a$ e $s_2 = \omega$ con $\omega$ una qualunque stringa definita sull'alfabeto $\Sigma = {a , b }$.
Sappiamo che le espressioni regolari definiscono un linguaggio in particolare nel nostro caso $L(r) = L(a) L((a | b)^*) L(a)$ allora $r$ catturerà le espressioni del linguaggio se e solo se $s_1 , s_3 in L(a)$ e $s_2 in L((a | b )^*)$, e siccome è vero che vi appartengono, per motivi anche ovvi. Allora la $r$ cattura tutte le stringhe del linguaggio.
2. $r$ cattura solo stringhe di $L$
Come dimostro questo punto? Considerando ciò che abbiamo appena dimostrato io pensavo di procedere nel modo seguente.
Sicuramente $r$ cattura $\omega = c_1 c_2 ... c_n$ tale che risulta $\{(c_1 = a),(c_n = a), (c_i = a vv c_i = b 2 <= i <= n - 1),(n >= 2):}$
Ora se $\omega notin L$ segue che almeno una delle condizioni del sistema non è verificata, per cui analizziamole una per una.
a) supponiamo per assurdo $c_1 != a$ questo significa che esiste una stringa del tipo $s = c_1 \omega a$ che è generabile dal linguaggio definito da $r$. Tuttavia sappiamo che $L(r) = L(a) L((a | b)^*) L(a)$ e se $c_1 != a$ allora $c_1 notin L(a)$ ma da ciò segue che $s notin L(r)$ e quindi non è generabile dal linguaggio
b) supponiamo per assurdo che $c_n != a$, con considerazioni analoghe al punto a) si dimostra che se ciò è vero non è catturabile dall'espressione regolare.
c) supponiamo per assurdo che esista almeno un $i : 2 <= i <= n - 1$ tale che $c_i != a ^^ c_i != b$ se ciò è vero stiamo ammettendo che esista almeno una stringa $s = a \omega a$ tale che $\omega$ contenga almeno un simbolo non appartenente all'alfabeto $Sigma = {a , b}$ ma se ciò è vero significa che $\omega$ è catturata dall'espressione regolare $r_\xi = (a | b | \xi )^*$ e questa espressione regolare cattura in particolar modo la stringa $s_\xi = \xi$ che non appartiene a $L(( a | b )^*)$. Da quanto detto segue che $s$ non è generabile dal linguaggio $L$.
d) Se $n < 2$ le uniche stringhe ammissibili sarebbero solo quelle di lunghezza $l < 2$ ma ciò è un'assurdo perchè la stringa $s = aa$ è catturata dal linguaggio.
In conclusione chiedo
1. La dimostrazione è corretta?
2. Una dimostrazione di questa natura è troppo lunga? esistono modi più semplici per dimostrare la validità di un'affermazione su un espressione regolare.
Se si vuol dimostrare che una espressione regolare $r$ definisce un certo linguaggio $L$ si procede in 2 passi? Come per la grammatiche intendo...ovvero.
1. Tutte le stringhe di $L$ sono catturate da $r$
2. $r$ cattura solo stringhe di $L$
Per le grammatiche invece si procede, in generale
1. $G$ genera stringhe di $L$
2. Tutte le stringhe di $L$ sono generate da $G$
Nel caso delle espressioni regolari in particolare se per esempio prendo la seguente
$r = a ( a | b )^* a$
questa espressione cattura, e si vede ad occhio, tutte le stringhe definite sull'alfabeto $\Sigma = { a , b }$ che iniziano e finiscono per $a$
Per dimostrare però che è vero ciò che dico considero
1. Tutte le stringhe di $L$ sono catturate da $r$
La generica stringa di $L$ è una stringa del tipo $a \omega a$ questa stringa la possiamo vedere come concatenazione di tre stringhe
$s_1 = s_3 = a$ e $s_2 = \omega$ con $\omega$ una qualunque stringa definita sull'alfabeto $\Sigma = {a , b }$.
Sappiamo che le espressioni regolari definiscono un linguaggio in particolare nel nostro caso $L(r) = L(a) L((a | b)^*) L(a)$ allora $r$ catturerà le espressioni del linguaggio se e solo se $s_1 , s_3 in L(a)$ e $s_2 in L((a | b )^*)$, e siccome è vero che vi appartengono, per motivi anche ovvi. Allora la $r$ cattura tutte le stringhe del linguaggio.
2. $r$ cattura solo stringhe di $L$
Come dimostro questo punto? Considerando ciò che abbiamo appena dimostrato io pensavo di procedere nel modo seguente.
Sicuramente $r$ cattura $\omega = c_1 c_2 ... c_n$ tale che risulta $\{(c_1 = a),(c_n = a), (c_i = a vv c_i = b 2 <= i <= n - 1),(n >= 2):}$
Ora se $\omega notin L$ segue che almeno una delle condizioni del sistema non è verificata, per cui analizziamole una per una.
a) supponiamo per assurdo $c_1 != a$ questo significa che esiste una stringa del tipo $s = c_1 \omega a$ che è generabile dal linguaggio definito da $r$. Tuttavia sappiamo che $L(r) = L(a) L((a | b)^*) L(a)$ e se $c_1 != a$ allora $c_1 notin L(a)$ ma da ciò segue che $s notin L(r)$ e quindi non è generabile dal linguaggio
b) supponiamo per assurdo che $c_n != a$, con considerazioni analoghe al punto a) si dimostra che se ciò è vero non è catturabile dall'espressione regolare.
c) supponiamo per assurdo che esista almeno un $i : 2 <= i <= n - 1$ tale che $c_i != a ^^ c_i != b$ se ciò è vero stiamo ammettendo che esista almeno una stringa $s = a \omega a$ tale che $\omega$ contenga almeno un simbolo non appartenente all'alfabeto $Sigma = {a , b}$ ma se ciò è vero significa che $\omega$ è catturata dall'espressione regolare $r_\xi = (a | b | \xi )^*$ e questa espressione regolare cattura in particolar modo la stringa $s_\xi = \xi$ che non appartiene a $L(( a | b )^*)$. Da quanto detto segue che $s$ non è generabile dal linguaggio $L$.
d) Se $n < 2$ le uniche stringhe ammissibili sarebbero solo quelle di lunghezza $l < 2$ ma ciò è un'assurdo perchè la stringa $s = aa$ è catturata dal linguaggio.
In conclusione chiedo
1. La dimostrazione è corretta?
2. Una dimostrazione di questa natura è troppo lunga? esistono modi più semplici per dimostrare la validità di un'affermazione su un espressione regolare.
Risposte
Come procedi con le grammatiche in generale? Allora prova: trasformi la regex in grammatica (regolare).
Sarò sincero...non c'avevo pensato...però considerando che "cronologicamente" le espressioni regolari vengono prima delle grammatiche, volevo trovare una dimostrazione alternativa.
Scusa tu come dimostreresti che questa espressione regolare
$r = ( a a | b b )*((ab|ba)(a a | b b)*(ab|ba)(a a | b b)*)*$
genera il suo linguaggio? useresti le grammatiche?
In effetti però se uno ha dimestichezza con le grammatiche potrebbe essere una buona strada...
P.S. L'espressione che ho scritto AD OCCHIO dovrebbe generare le stringhe definite sull'alfabeto $\Sigma = { a , b }$ con numero di $a$ pari e numero di $b$ pari.
Scusa tu come dimostreresti che questa espressione regolare
$r = ( a a | b b )*((ab|ba)(a a | b b)*(ab|ba)(a a | b b)*)*$
genera il suo linguaggio? useresti le grammatiche?
In effetti però se uno ha dimestichezza con le grammatiche potrebbe essere una buona strada...
P.S. L'espressione che ho scritto AD OCCHIO dovrebbe generare le stringhe definite sull'alfabeto $\Sigma = { a , b }$ con numero di $a$ pari e numero di $b$ pari.
Numero pari di 'a' e 'b', direi anch'io; riscrivo ché non si vede bene '*'
$(aa|bb)\star((ab|ba)(aa|bb)\star(ab|ba)(aa|bb)\star)\star$
Dopo puoi definire l'automa che accetta la regex, e che quindi accetta il linguaggio. Poi da questo definisci la grammatica - con un po' di accortezza puoi evitare un passaggio e definire direttamente la grammatica.
Se definisci l'automa rigorosamente hai ogni transizione con un solo simbolo o vuota, da questa generi una regola della grammatica. Comincio io
$S->aA|bB|epsilon$
$A->aC|E$
$B->bD|F$
$C->aA$
$D->bB$
$E->$ ...
eccetera.
Per rispondere alla tua domanda: userei la grammatica per dimostrare che una regex definisce un particolare linguaggio? Non ci ho mai pensato, perché le regex sono "semplici" ed in genere il risultato è autoevidente, ma del resto se definisci la grammatica sei a posto. E' un procedimento facile, solo un po' noioso
$(aa|bb)\star((ab|ba)(aa|bb)\star(ab|ba)(aa|bb)\star)\star$
Dopo puoi definire l'automa che accetta la regex, e che quindi accetta il linguaggio. Poi da questo definisci la grammatica - con un po' di accortezza puoi evitare un passaggio e definire direttamente la grammatica.
Se definisci l'automa rigorosamente hai ogni transizione con un solo simbolo o vuota, da questa generi una regola della grammatica. Comincio io
$S->aA|bB|epsilon$
$A->aC|E$
$B->bD|F$
$C->aA$
$D->bB$
$E->$ ...
eccetera.
Per rispondere alla tua domanda: userei la grammatica per dimostrare che una regex definisce un particolare linguaggio? Non ci ho mai pensato, perché le regex sono "semplici" ed in genere il risultato è autoevidente, ma del resto se definisci la grammatica sei a posto. E' un procedimento facile, solo un po' noioso
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo