Linguaggio regolare Pumping Lemma
Ho il seguente esercizio:
dato il Linguaggio \(\displaystyle L \) sull'alfabeto \(\displaystyle \{a,b\}^*\), definisco \(\displaystyle L_1=\{v \in \{a,b\}^* : (u^Rv^R)^R \) per qualche \(\displaystyle u \in \{a,b\}^*\} \)
dove se \(\displaystyle v=a_1a_2...a_r \) allora \(\displaystyle v^R=a_ra_{r-1}...a_1\).
Devo dire se \(\displaystyle L \) è regolare e se è context-free.
Devo applicare il Pumping Lemma...
Intanto \(\displaystyle (u^Rv^R)^R \) dovrebbe essere uguale a \(\displaystyle vu \), in tal caso qualsiasi fattorizzazione prendo della parola \(\displaystyle vu \) e preso qualsiasi blocco iterante in \(\displaystyle v \) dovrei ottenere una stringa riconosciuta dal linguaggio o no???
Per favore qualcuno mi aiuti perchè non so ancora ragionare bene con il Pumping Lemma sia per i linguaggi regolari che per quelli context-free.
dato il Linguaggio \(\displaystyle L \) sull'alfabeto \(\displaystyle \{a,b\}^*\), definisco \(\displaystyle L_1=\{v \in \{a,b\}^* : (u^Rv^R)^R \) per qualche \(\displaystyle u \in \{a,b\}^*\} \)
dove se \(\displaystyle v=a_1a_2...a_r \) allora \(\displaystyle v^R=a_ra_{r-1}...a_1\).
Devo dire se \(\displaystyle L \) è regolare e se è context-free.
Devo applicare il Pumping Lemma...
Intanto \(\displaystyle (u^Rv^R)^R \) dovrebbe essere uguale a \(\displaystyle vu \), in tal caso qualsiasi fattorizzazione prendo della parola \(\displaystyle vu \) e preso qualsiasi blocco iterante in \(\displaystyle v \) dovrei ottenere una stringa riconosciuta dal linguaggio o no???
Per favore qualcuno mi aiuti perchè non so ancora ragionare bene con il Pumping Lemma sia per i linguaggi regolari che per quelli context-free.
Risposte
Non riesco proprio a capire... il testo è proprio come l'hai riportato?
Hai ragione il linguaggio di cui dovrei provare se è regolare e context-free è \(\displaystyle L_1 \)
Avevo dimenticato il pedice... sorry!! :S
Avevo dimenticato il pedice... sorry!! :S
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo