vfldj
12-03-2013, 19:43
Ciao, sono giorni che studio Linguaggi di programmazione ma non riesco ad applicare la teoria alla pratica. Come faccio a capire in modo pratico se un linguaggio è regolare, context-free o non context-free? C'è un metodo immediato o quasi per saperlo? Il pumping lemma non l'ho capito molto bene.
Ciò che ho capito è che un linguaggio del genere {a^n b^m | n>=0} non è regolare perchè chiede che ci siano un numero "preciso" di a e di b e questo non è possibile con i linguaggi regolari. E' giusto come ragionamento? A me sembra un pò vago...
E per i context-free?
Per esempio questi linguaggi cosa sono?
- L_1 = {a b^n a b^(2n) |n > 0}
- L_2 = {a b^n c^k a^n b^k |k,n > 0}
- L_3 = {a b^n ab^(2n) a b^(3n)|n > 0}
-L_4 = {a b^n b^k a^n b^k |k,n > 0}
Grazie mille :)
Ciò che ho capito è che un linguaggio del genere {a^n b^m | n>=0} non è regolare perchè chiede che ci siano un numero "preciso" di a e di b e questo non è possibile con i linguaggi regolari. E' giusto come ragionamento? A me sembra un pò vago...
E per i context-free?
Per esempio questi linguaggi cosa sono?
- L_1 = {a b^n a b^(2n) |n > 0}
- L_2 = {a b^n c^k a^n b^k |k,n > 0}
- L_3 = {a b^n ab^(2n) a b^(3n)|n > 0}
-L_4 = {a b^n b^k a^n b^k |k,n > 0}
Grazie mille :)