Matematicamente.it

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.

up

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\).

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?

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.

perfetto,grazie dell'aiuto.provo a fare qualche altro esercizio col pumping lemma sperando di cavarmela.