Pages: [1]   Go Down
Print
Author Topic: Dimostrazione Linguaggio irregolare  (Read 1416 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Charlemagne
Matricola
*
Offline Offline

Gender: Male
Posts: 10



WWW
« on: 17-01-2019, 21:57:36 »

Pubblico la mia risoluzione dell'esercizio poiché vorrei capire se è corretto o meno:

Si dimostri che L = { A^h B^k | h,k > 0 , h > k } è irregolare.

Se L fosse irregolare, tramite la "tecnica dell'avversario" esisterebbe una z in cui il Pumping Lemma non viene soddisfatto.

z = uvw dove |u| >= 1 , |uv| <= n

prendo in considerazione la stringa z = { A ^ 2/3n B ^ 1/3n ), quest'ultima può essere utilizzata nel PL poiché |z| = 2/3n + 1/3n >= n  e soprattutto è appartenente a L poiche 2/3n > 1/3n ed entrambi sono diversi da 0.

Consideriamo uv =  A ^ 2/3n B ^ 1/3n  (sto ancora rispettando le condizioni, |uv| <= n )

e consideriamo u = A ^ 2/3n     v = B ^ 1/3n

applicando il Pumping lemma, aggiungiamo iesime v alla stringa z ( u v^i z )

ma così facendo raggiungeremo sicuramente una stringa con maggiori B rispetto ad A, quella stringa non sarà appartenente ad L e non soddisferà quindi il Pumping Lemma.

Di conseguenza, L è irregolare.

Chiedo gentilmente dei feedback,
Buona serata.

Logged

Rotlaust tre fell
Marina Madonia
Moderator
Matricola
*****
Offline Offline

Posts: 55


« Reply #1 on: 22-01-2019, 22:37:43 »

La dimostrazione non è corretta. Infatti per dimostrare che L non soddisfa il Pumping lemma, bisogna dimostrare che, PER OGNI modo di dividere z in uvw, esiste un indice i tale che uv^iw non appartiene ad L. Nella Sua dimostrazione invece Lei ha considerato soltanto un possibile modo di dividere z in uvw e, per questo caso particolare, ha dimostrato che esiste un indice i tale che uv^iw non appartiene ad L.

Logged
mordom
Matricola
*
Offline Offline

Posts: 14


« Reply #2 on: 24-01-2019, 16:50:47 »

Salve,
provo a risolvere.

Sia n la costante che il Pumping Lemma ci suggerisce.
Consideriamo la stringa, appartenente al linguaggio, z = an+1bn . La sua lunghezza è |z| > n .
Possiamo quindi decomporla in tre sottostringhe, z = uvw con |uv|<= n e |v|>= 1 .
Poiché |uv|<=n , la sottostringa v sarà composta solamente di a.
Sempre in riferimento al Pumping Lemma se z è regolare, allora, uviw , Forall i >=0 dovrà ancora appartenere al linguaggio.
Considerando i=0, il numero di a della stringa non è più maggiore del numero di b e di conseguenza non appartiene al linguaggio L = { A^h B^k | h,k > 0 , h > k }.
Quindi, quest'ultimo, non è regolare.
Logged
Marina Madonia
Moderator
Matricola
*****
Offline Offline

Posts: 55


« Reply #3 on: 24-01-2019, 17:46:37 »

Così è quasi perfetto... soltanto invece che scrivere
 
"Possiamo quindi decomporla in tre sottostringhe, z = uvw con |uv|<= n e |v|>= 1 .
Poiché |uv|<=n ,"

sarebbe più corretto scrivere

"Per ogni modo di decomporre z in tre sottostringhe , z = uvw con |uv|<= n e |v|>= 1, poiché |uv|<=n, la sottostringa v sarà composta solamente di a."

Un'altra osservazione: l'aggettivo regolare NON si riferisce a stringhe (NON si può dire "la stringa z è regolare") ma si riferisce a linguaggi (si dice "il linguaggio L è regolare").
M. Madonia
Logged
mordom
Matricola
*
Offline Offline

Posts: 14


« Reply #4 on: 24-01-2019, 17:59:52 »

Se z è regolare...
Scusi prof! orribile svista!

Per il resto, la ringrazio infinitamente!
Logged
Charlemagne
Matricola
*
Offline Offline

Gender: Male
Posts: 10



WWW
« Reply #5 on: 24-01-2019, 18:16:14 »

Ho capito dove sta l'errore.. posto I, devo garantire che tutte le combinazioni che rispettino le condizioni |uv|<= n e |v|>= 1 non soddisfino il pumping lemma.

Grazie mille, buona serata
Logged

Rotlaust tre fell
Pages: [1]   Go Up
Print
Jump to: