Esercizio pumping lemma

Messaggioda Brufus » 06/09/2018, 13:06

Sia L il linguaggio costituito dalle parole z della forma
z= xaavaay dove x e y sono parole qualsiasi anche vuote, v è di lunghezza pari,non vuota e contiene aa esattamente al centro.
Devo provare tramite pumping lemma che tale linguaggio non è regolare.
Avatar utente
Brufus
Average Member
Average Member
 
Messaggio: 3 di 525
Iscritto il: 05/02/2016, 00:44
Località: Roma

Re: Esercizio pumping lemma

Messaggioda Brufus » 03/02/2019, 13:45

up
Avatar utente
Brufus
Average Member
Average Member
 
Messaggio: 5 di 525
Iscritto il: 05/02/2016, 00:44
Località: Roma

Re: Esercizio pumping lemma

Messaggioda apatriarca » 03/02/2019, 19:23

Ciao, la descrizione del linguaggio è un po' poco precisa. In linea di massima il linguaggio non è regolare in quanto la stringa \(v\) richiede che \(aa\) sia esattamente al centro. Puoi usare come controesempio per il pumping lemma stringhe della forma \(aab^naac^naa\). Queste stringhe rispettano la tua descrizione con \(x\) e \(y\) stringhe vuote e \(v = b^naac^n\). Supponiamo che esista un \(p\) come nel lemma e prendiamo quindi la stringa \(aab^paac^paa\) che è più lunga di \(p\). Dobbiamo quindi avere una decomposizione \(aab^paac^paa = xyz\) per cui \(|xy| \leq p\) e \(|y| \geq 1\) per cui \(xy^iz\) appartiene al linguaggio. Abbiamo che \(y\) è necessariamente formato da solo \(b\) o uguale a uno tra \(aab^{t}\) o \(ab^{s}\). Se fosse solo \(b\) allora chiaramente non si avrebbe più un \(aa\) al centro di \(v\) e quindi la parola non fa parte del linguaggio. Discorso simile vale nel caso in cui ci fosse una sola \(a\). L'unica possibilità che è rimasta è quindi che \(y\) inizi con \(aa\). In questo caso otteniamo la stringa \((aab^t)^ib^{p-t}aac^paa\). Ma anche in questo caso la stringa non appartiene al linguaggio con \(i = 0\).
apatriarca
Moderatore
Moderatore
 
Messaggio: 5183 di 10435
Iscritto il: 08/12/2008, 20:37
Località: Madrid

Re: Esercizio pumping lemma

Messaggioda Brufus » 04/02/2019, 03:22

grazie per avermi risposto.preciso che l'alfabeto su cui lavoriamo è costituito dalle lettere a,b.
potresti spiegarmi nella decomposizione $xyz$ quali sarebbero le parole $x$ ed $y$?
dovendo valere $|xy|<=p$ ed essendo la nostra parola della forma $aab^paab^paa$ necessariamente sarà $xy = aab^(p-2)$ giusto?E dovendo per forza di cosa essere $|y|>=1$ i casi possibili sarebbero:

1)$y=b^t,1<=t<=p-2$
2)$y= ab^(p-2)$
3)$y=aab^(p-2)$.
sto sbagliando nel ragionamento?era questo ciò che intendevi tu?
Inoltre vorrei capire una sottigliezza.Nell'utilizzare il pumping lemma per dimostrare la non regolarità di un linguaggio cosa cambia nell'avvalersi della contronominale,(ovverosia far vedere che $forall n in N$ esiste una parola $w,|w|>=n$ tale che per ogni decomposizione $w=xyz, |xy|<=n,|y|>=1,xy^iz notin L$ per almeno un $i >=0$)oppure la dimostrazione per assurdo che tu stai usando in questa sede?
Avatar utente
Brufus
Average Member
Average Member
 
Messaggio: 6 di 525
Iscritto il: 05/02/2016, 00:44
Località: Roma

Re: Esercizio pumping lemma

Messaggioda apatriarca » 04/02/2019, 03:28

Era quello che intendevo. La scelta del metodo usato è una preferenza personale. In questa sede mi sono ispirato ad un testo che usava la dimostrazione per assurdo e quindi l'ho scritta così, ma altri metodi sono certamente validi. Usa quella che trovi più comoda.
apatriarca
Moderatore
Moderatore
 
Messaggio: 5185 di 10435
Iscritto il: 08/12/2008, 20:37
Località: Madrid

Re: Esercizio pumping lemma

Messaggioda Brufus » 04/02/2019, 03:44

perfetto,grazie dell'aiuto.provo a fare qualche altro esercizio col pumping lemma sperando di cavarmela.
Avatar utente
Brufus
Average Member
Average Member
 
Messaggio: 8 di 525
Iscritto il: 05/02/2016, 00:44
Località: Roma


Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite