Linguaggio regolare
Ciao a tutti, vorrei una mano su questo esercizio, data la grammatica:
S::=aSS|b
dire se il linguaggio è regolare, dimostrare questo cn il pumping lemma.
Ora la grammatica non dovrebbe essere regolare ma context free, in quanto nella parte destra della produzione sono presenti due non terminali. In pù dato l'equivalenza fra le espressioni regolari e gli automi sappiamo che non è regolare in quanto l'automa non sa contare. Infatti quel linguaggio denota gli alberi binari, o comunque tutte le stringhe dove vi sono un numero di b maggiori di 1 rispetto alle a.
Come faccio a dimostrare la non regolarità del linguaggio con il pumping lemma?
grazie in anticipo.
S::=aSS|b
dire se il linguaggio è regolare, dimostrare questo cn il pumping lemma.
Ora la grammatica non dovrebbe essere regolare ma context free, in quanto nella parte destra della produzione sono presenti due non terminali. In pù dato l'equivalenza fra le espressioni regolari e gli automi sappiamo che non è regolare in quanto l'automa non sa contare. Infatti quel linguaggio denota gli alberi binari, o comunque tutte le stringhe dove vi sono un numero di b maggiori di 1 rispetto alle a.
Come faccio a dimostrare la non regolarità del linguaggio con il pumping lemma?
grazie in anticipo.
Risposte
Hai (correttamente) concluso che la grammatica esprime un linguaggio libero da contesto.
Puoi adesso usare il pumping lemma per linguaggi regolari, per dimostrare appunto che il linguaggio corrispondente non lo è. Quindi parti da qui: cosa dice il puimping lemma per linguaggi regolari?
Puoi adesso usare il pumping lemma per linguaggi regolari, per dimostrare appunto che il linguaggio corrispondente non lo è. Quindi parti da qui: cosa dice il puimping lemma per linguaggi regolari?
Dice: Sia Lun linguaggio regolare. Allora esite una costante n tale che, per ogni stringa w in L per la quale la sua cardinalità è >= n, possiamo scomporre w in tre stringe w=xyz tale che:
y è diverso dalla parola vuota, cardinalità di xy < n , per ogni k>=0 anche xy^kz è in L.
Puoi aiutarmi ad applicarlo in questo esercizio?
y è diverso dalla parola vuota, cardinalità di xy < n , per ogni k>=0 anche xy^kz è in L.
Puoi aiutarmi ad applicarlo in questo esercizio?
Perfetto. Prendi quindi il tuo linguaggio $L$; supponi esista il tuo $n$, che sia pari (il caso $n$ dispari è analogo) e che quindi la stringa $w=a^m b^(m+1)$ con $m=n/2$ possa venir scomposta come visto in $w=xyz$ tc. $|y|>0$ e $|xy|<=n$; a questo punto puoi scomporre i casi:
- $y$ è composta da sole 'a' (è della forma $y=a^k$)
- $y$ è composta da sole 'b' ($y=b^h$)
- $y$ è composta da 'a' e 'b'($y=a^k b^h$)
puoi dimostrare agevolmente che comunque caso si presenti e per qualunque $k, h$ si ha $xy^iz notin L$ per qualche $i>=0$, prova.
- $y$ è composta da sole 'a' (è della forma $y=a^k$)
- $y$ è composta da sole 'b' ($y=b^h$)
- $y$ è composta da 'a' e 'b'($y=a^k b^h$)
puoi dimostrare agevolmente che comunque caso si presenti e per qualunque $k, h$ si ha $xy^iz notin L$ per qualche $i>=0$, prova.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo