Ascoltate mi piacerebbe prendere 10 punti su questo esercizio, ma non so da dv cominciare x svolgerlo. Qualcuno potrebbe indicarmi i passi da seguire ed eventualmente scrivere se c'¨¨ bisogno la grammatica che genera il linguaggio? Grazie x l'aiuto
1) Stabilire se il seguente linguaggio:L = {abjacka : j,k ¡Ý 0} ¨¨ lineare destro. (PUNTI 2) Giustificare formalmente la risposta (PUNTI 8)
..siamo solo noi...generazione di sconvolti ke nn han + santi nè eroi...siamo solo noiiiiiiiiiiiiiiiiiii....
a b^j a c^k a è lineare destro poiché è concatenazione di linguaggi lineari destri...
S1 --> a S2 --> bS2 | lambda S3 --> a S4 --> cS4 | lambda S5 --> a
se percaso hai omesso di scrivere che j e k siano in una qualche relazione tra di loro es. diversi o uguali ecc. allora il linguaggio si dimostra essere non di tipo 3 con il pumping lemma per i linguaggi regolari...
Ok Sd83 ti ringrazio per avermi risposto quindi scrivendo la soluzione che mi hai proposto sicuramente dovrei prendere i due punti, ma per gli 8 devo dimostrare qualcosa in particolare? Grazie mille
..siamo solo noi...generazione di sconvolti ke nn han + santi nè eroi...siamo solo noiiiiiiiiiiiiiiiiiii....
se il linguaggio non è lineare destro lo dimostri formalmente col pumping lemma se è lineare destro lo dimostri formalmente trovando una grammatica lineare destra che lo genera