.dsy:it. (http://www.dsy.it/forum/)
- Linguaggi formali e automi (http://www.dsy.it/forum/forumdisplay.php?forumid=132)
-- Help pumping lemma (http://www.dsy.it/forum/showthread.php?threadid=41837)

Help pumping lemma

Pumping lemma:
"Sia L un linguaggio regolare. Esiste allora una costante N tale che, per ogni stringa w in L per la quale |w|>=N, possiamo scomporre w in tre stringhe w= xyz in modo che
(1) y diverso da epsilon (stringa vuota)
(2) |xy| <= N
(3) per ogni k >= 0 anche la stringa x y^k z è il L"

Questo teorema sembra non funzionare per il linguaggio regolare L="numero pari di a" in alfabeto {a,b}
infatti prendendo una stringa a caso w=aabaa
e dividendola in
x=a
y=a
z=baa
abbiamo le prime 2 condizioni verificate ma la terza no!
infatti per k=2 abbiamo la stringa aaabaa che viene accettata nonostante non abbia un numero pari di a.

Chi mi aiuta a trovare l'errore nel mio ragionamento??

Come la generi questa stringa "w=aabaa" ?

__________________
.. ±·ø·±-`` MuSiC iS My LanGuAGe ´´-±·ø·± ..

In che senso? Io ho scelto a caso una stringa con un numero pari di a..

Quindi hai scelto a caso una parola del linguaggio regolare generata dalla grammatica di tipo 3. Puoi scrivermi formalmente la regola di generazione che hai usato?

__________________
.. ±·ø·±-`` MuSiC iS My LanGuAGe ´´-±·ø·± ..

mattiie mi hai messo in crisi è mezz'ora che cerco di capire cosa c'è di sbagliato...
mi sa che non ho capito bene il P lemma. il tuo esempio (che mi sembra corretto) fa saltare in pieno il pumping lemma...
qualcuno ha idee?

Infatti! Quindi ci deve essere per forza un errore nel mio ragionamento.
Rispondo anche a CowBoy: non ho utilizzato nessuna regola di generazione; ho solo pensato ad una stringa che avesse un numero pari di a e la prima che mi è venuta in mente è w= aabaa ...

Sto uscendo di corsa quindi la prossima domanda ve la porrò dopo... Pensate per un attimo alle grammatiche di tipo 3, come sono formate e quali regole di produzione assumono. La parola scelta da mattie non fa parte del linguaggio regolare generato da una grammatica di tipo 3.

__________________
.. ±·ø·±-`` MuSiC iS My LanGuAGe ´´-±·ø·± ..

a parte wikipedia & co. ho davanti gli appunti del pighizzini

1) y diverso da vuota.
e qua il tuo esempio va bene
2) lunghezza xy <=N
beh anche qua non vedo nessun problema scegliamo N=3 ad esempio
3) per OGNI k>=0 x(y^k)z appartiene al linguaggio L
e qua salta tutto.


uffa





edit ho visto dopo cowboy, grammatiche tipo 3 intendi riconosciute da automa a stati finiti?

scusate doppio post e scusate lo schifo di disegno fatto in paint, l'automa da me disegnato accetta il linguaggio di mattie quindi il linguaggio è regolare, allora pechè il pumping lemma va in crisi?


come linguaggio ad esempio:

(aa)* + b*

Grammatica di tipo 3 lineare da destra o da sinistra, quelli riconosciuti da automi a stati finiti sono i linguaggi regolari.

L'automa descritto in quel modo è errato...

Cercando su google ho trovato queste slide dove vengono chiarite le definizioni formali di Grammatica, Linguaggio ed Espressione Regolare.

Se non ho dimenticato qualcosa l'insieme delle produzioni della grammatica contiene:

A-> bA
A-> aB
A-> b
B-> aA
B-> bB
B-> a

__________________
.. ±·ø·±-`` MuSiC iS My LanGuAGe ´´-±·ø·± ..

però col prof non abbiamo ancora fatto alcun accenno alle grammatiche di tipo 3 (nemmeno alle grammatiche in generale)
sul disegno hai ragione, totalmente errato, questo penso funzioni invece (manca solo un ciclo sullo stato finale se ricevo B rimango li)

Uno schema completo e più chiaro.

Adesso, applicando il pumping lemma, tutto dovrebbe funzionare senza problemi... fatemi sapere.

P.S.: Tutti gli automi a stati finiti hanno uno stato(cerchio) e una transizione(freccia) ed è meglio descrivere quest'ultimi con uno simbolo/nome.

__________________
.. ±·ø·±-`` MuSiC iS My LanGuAGe ´´-±·ø·± ..

ma il linguaggio postato da mattiie è regolare o no? o meglio non ho capito in cosa sia sbagliato il ragionamento di mattiie del primo post?

ps ma nel tuo schema per "regole" cosa intendi?


intanto grazie per le tante risposte

L'automa descritto in precedenza è a stati finiti non deterministico. Un linguaggio viene definito come regolare se può essere descritto da un'espressione regolare, accettato da un automa a stati finiti e generato da una grammatica di tipo 3 della gerarchia di Chomsky(lineare da destra o da sinistra).

mattie ha preso una stringa arbitraria con un numero pari di 'a'. Purtroppo questa stringa non fa parte dell'insieme delle parole del linguaggio regolare che voleva utilizzare portando all'assurdo il pumping lemma.

La grammatica di tipo 3 restringe le sue regole ad un singolo simbolo non terminale nel lato sinistro della produzione e nel lato destro un singolo simbolo terminale, che può essere seguito (o preceduto, ma non entrambe le forme nella stessa grammatica) da un singolo simbolo non terminale(per questo viene definito lineare da destra o da sinistra).

Una grammatica G è una quadrupla G = < N,T,S,P > , ove N è l'alfabeto terminale (le lettere di una parola nel linguaggio formale), T è l'insieme dei metasimboli (l'alfabeto non terminale ovvero le lettere in maiuscolo), P è una relazione binaria di cardinalità in altre parole un insieme di regole di produzione (con un lato sinistro ed un lato destro), ed infine S appartenente a T ed è detto Assioma o simbolo di inizio.
Una regola di produzione può essere applicata ad una parola rimpiazzando il lato sinistro con il lato destro. Una derivazione è una sequenza di regole di produzione. In questo modo una grammatica definisce un linguaggio formale con tutte le parole costituite dai soli simboli terminali che possono essere raggiunti dal simbolo iniziale attraverso derivazioni.

Esempio basato sulle regole definite nel post precedente:

A-> bA : questa è una regola dove 'A' è un metasimbolo e 'b' è un simbolo terminale. Potete vedere 'A' come "qualcosa da rimpiazzare"; potete vedere la regola come una funzione matematica che associa ad 'A' il valore della regola di produzione 'bA'.
A-> b : è anche questa una regola di produzione che associa al metasimbolo 'A' il simbolo terminale 'b'.

A-> bA-> bb : questa è una derivazione; applicando le regole di produzione si arriva a formare una parola del linguaggio



P.S.: Ho usato wikipedia semplificando alcune info secondo le dispense della Prof. Palano con la quale ho seguito il corso un paio di anni fa.

http://it.wikipedia.org/wiki/Gerarchia_di_Chomsky
http://it.wikipedia.org/wiki/linguaggio_regolare

__________________
.. ±·ø·±-`` MuSiC iS My LanGuAGe ´´-±·ø·± ..

Originally posted by CowBoy
......

La grammatica di tipo 3 restringe le sue regole ad un singolo simbolo non terminale nel lato sinistro della produzione e nel lato destro un singolo simbolo terminale, che può essere seguito (o preceduto, ma non entrambe le forme nella stessa grammatica) da un singolo simbolo non terminale(per questo vieni definito lineare da destra o da sinistra).
.......