pumping lemma...

[mictrt]

Sia L2 il linguaggio su Σ = {a, b} delle parole del tipo waaw tali che w ∈ Σ∗ contiene un numero pari di a oppure ubbu tali che u ∈ Σ∗ contiene un numero dispari di a. Dimostrare, usando il pumping lemma, che L2 non ́e regolare.


non riesco a "creare" L2..... consigli?

[mictrt]

non capisco come faccio a scrivere il linguaggio...poi in teoria applicare il pumping lemma dovrebbe essere facile...

[Rggb]

Non hai necessità di "scrivere" il linguaggio, è sufficiente la descrizione che già hai. Parti dal PL per linguaggi regolari, cosa ti dice? Applica la definizione ad una generica stringa \( \displaystyle {w}{a}{a}{w} \) (l'altro caso è equivalente).

[mictrt]

grazie Rggb domattina provo e posto la soluzione....


consigli sugli altri esercizi?

[mictrt]

grazie all'aiuto dell'amico rggb... penso di aver trovato una soluzione...

waaw -->> ho considerato questa parola perchè mi faceva comodo -->> a^n aa a^n

ho spezzato la parola cosi' a a^(n-1) aa a^n

x=a

y= a^(n-1)

z=aa a^n


dopodichè per le 3 regolette

1) | a^(n-1) | >0 vero

2) | aa^(n-1)|<= n vero


3) a(a^(n-1))^i aa a^n Falso perchè il numero di a per una qualsisasi i restituisce numero pari,ma secondo il testo il numero di a deve essere pari...


quindi linguaggio non regolare