Dsy Network www | forum | my | didattica | howto | wiki | el goog | stats | blog | dona | rappresentanti
Homepage
 Register   Calendar   Members  Faq   Search  Logout 
.dsy:it. : Powered by vBulletin version 2.3.1 .dsy:it. > Didattica > Corsi G - M > Linguaggi formali e automi > Help pumping lemma
Pages (2): [1] 2 »   Last Thread   Next Thread
Author
Thread    Post New Thread    Post A Reply
mattiie
dsy developer

User info:
Registered: Oct 2010
Posts: 46 (0.01 al dì)
Location: milano
Corso: Informatica F94
Anno: Primo (Magistrale)
Time Online: 9:28:41 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged
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??

14-04-2011 12:31
Click Here to See the Profile for mattiie Click here to Send mattiie a Private Message Find more posts by mattiie Add mattiie to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
CowBoy
.arcimaestro.

User info:
Registered: May 2006
Posts: 294 (0.06 al dì)
Location: Milano
Corso: F49 - Informatica
Anno: Laureato F49
Time Online: 3 Days, 13:40:27 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

Come la generi questa stringa "w=aabaa" ?

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

14-04-2011 14:45
Click Here to See the Profile for CowBoy Click here to Send CowBoy a Private Message Find more posts by CowBoy Add CowBoy to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
mattiie
dsy developer

User info:
Registered: Oct 2010
Posts: 46 (0.01 al dì)
Location: milano
Corso: Informatica F94
Anno: Primo (Magistrale)
Time Online: 9:28:41 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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

14-04-2011 17:22
Click Here to See the Profile for mattiie Click here to Send mattiie a Private Message Find more posts by mattiie Add mattiie to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
CowBoy
.arcimaestro.

User info:
Registered: May 2006
Posts: 294 (0.06 al dì)
Location: Milano
Corso: F49 - Informatica
Anno: Laureato F49
Time Online: 3 Days, 13:40:27 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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 ´´-±·ø·± ..

14-04-2011 21:46
Click Here to See the Profile for CowBoy Click here to Send CowBoy a Private Message Find more posts by CowBoy Add CowBoy to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
zandrek
.fedelissimo.

User info:
Registered: Oct 2003
Posts: 59 (0.01 al dì)
Location: Milano
Corso: Informatica
Anno:
Time Online: 21:43:33 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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?

16-04-2011 09:52
Click Here to See the Profile for zandrek Click here to Send zandrek a Private Message Find more posts by zandrek Add zandrek to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
mattiie
dsy developer

User info:
Registered: Oct 2010
Posts: 46 (0.01 al dì)
Location: milano
Corso: Informatica F94
Anno: Primo (Magistrale)
Time Online: 9:28:41 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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

16-04-2011 10:27
Click Here to See the Profile for mattiie Click here to Send mattiie a Private Message Find more posts by mattiie Add mattiie to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
CowBoy
.arcimaestro.

User info:
Registered: May 2006
Posts: 294 (0.06 al dì)
Location: Milano
Corso: F49 - Informatica
Anno: Laureato F49
Time Online: 3 Days, 13:40:27 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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 ´´-±·ø·± ..

16-04-2011 11:19
Click Here to See the Profile for CowBoy Click here to Send CowBoy a Private Message Find more posts by CowBoy Add CowBoy to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
zandrek
.fedelissimo.

User info:
Registered: Oct 2003
Posts: 59 (0.01 al dì)
Location: Milano
Corso: Informatica
Anno:
Time Online: 21:43:33 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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?

Last edited by zandrek on 16-04-2011 at 11:26

16-04-2011 11:19
Click Here to See the Profile for zandrek Click here to Send zandrek a Private Message Find more posts by zandrek Add zandrek to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
zandrek
.fedelissimo.

User info:
Registered: Oct 2003
Posts: 59 (0.01 al dì)
Location: Milano
Corso: Informatica
Anno:
Time Online: 21:43:33 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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*

Last edited by zandrek on 16-04-2011 at 12:28

16-04-2011 11:26
Click Here to See the Profile for zandrek Click here to Send zandrek a Private Message Find more posts by zandrek Add zandrek to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
CowBoy
.arcimaestro.

User info:
Registered: May 2006
Posts: 294 (0.06 al dì)
Location: Milano
Corso: F49 - Informatica
Anno: Laureato F49
Time Online: 3 Days, 13:40:27 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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 ´´-±·ø·± ..

Last edited by CowBoy on 16-04-2011 at 12:25

16-04-2011 11:55
Click Here to See the Profile for CowBoy Click here to Send CowBoy a Private Message Find more posts by CowBoy Add CowBoy to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
zandrek
.fedelissimo.

User info:
Registered: Oct 2003
Posts: 59 (0.01 al dì)
Location: Milano
Corso: Informatica
Anno:
Time Online: 21:43:33 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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)

Attachment: 16042011176.jpg
This has been downloaded 19 time(s).

16-04-2011 12:28
Click Here to See the Profile for zandrek Click here to Send zandrek a Private Message Find more posts by zandrek Add zandrek to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
CowBoy
.arcimaestro.

User info:
Registered: May 2006
Posts: 294 (0.06 al dì)
Location: Milano
Corso: F49 - Informatica
Anno: Laureato F49
Time Online: 3 Days, 13:40:27 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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.

Attachment: asf.jpg
This has been downloaded 15 time(s).

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

Last edited by CowBoy on 17-04-2011 at 00:39

16-04-2011 21:03
Click Here to See the Profile for CowBoy Click here to Send CowBoy a Private Message Find more posts by CowBoy Add CowBoy to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
zandrek
.fedelissimo.

User info:
Registered: Oct 2003
Posts: 59 (0.01 al dì)
Location: Milano
Corso: Informatica
Anno:
Time Online: 21:43:33 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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

18-04-2011 08:39
Click Here to See the Profile for zandrek Click here to Send zandrek a Private Message Find more posts by zandrek Add zandrek to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
CowBoy
.arcimaestro.

User info:
Registered: May 2006
Posts: 294 (0.06 al dì)
Location: Milano
Corso: F49 - Informatica
Anno: Laureato F49
Time Online: 3 Days, 13:40:27 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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 ´´-±·ø·± ..

Last edited by CowBoy on 18-04-2011 at 17:39

18-04-2011 12:05
Click Here to See the Profile for CowBoy Click here to Send CowBoy a Private Message Find more posts by CowBoy Add CowBoy to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
zandrek
.fedelissimo.

User info:
Registered: Oct 2003
Posts: 59 (0.01 al dì)
Location: Milano
Corso: Informatica
Anno:
Time Online: 21:43:33 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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



innanzitutto grazie per l'esaustiva e chiara risposta, in effetti mi è bastato leggere (e capire) la parte che ho quotato)
grazie anche per i link, ora però mi chiedo se i dubbi (miei e di mattie) non siano dovuti al fatto che il prof non è arrivato a spiegare quel che tu hai chiarito nel tuo post...
magari bastava aspettare domani però mattie mi ha messo una mega pulce nell'orecchio....

grazie ancora...

18-04-2011 17:24
Click Here to See the Profile for zandrek Click here to Send zandrek a Private Message Find more posts by zandrek Add zandrek to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
All times are GMT. The time now is 01:02.    Post New Thread    Post A Reply
Pages (2): [1] 2 »   Last Thread   Next Thread
Show Printable Version | Email this Page | Subscribe to this Thread | Add to Bookmarks

Forum Jump:
Rate This Thread:

Forum Rules:
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is OFF
vB code is ON
Smilies are ON
[IMG] code is ON
 

Powered by: vBulletin v2.3.1 - Copyright ©2000 - 2002, Jelsoft Enterprises Limited
Mantained by dsy crew (email) | Collabora con noi | Segnalaci un bug | Archive | Regolamento | Licenze | Thanks | Syndacate
Pagina generata in 0.051 seconds (65.83% PHP - 34.17% MySQL) con 25 query.