Pages: [1]   Go Down
Print
Author Topic: esercizio 2.1 pag 41 dell' ausiello  (Read 138 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
luca98
Matricola
*
Offline Offline

Posts: 34


« on: 16-11-2017, 16:33:35 »

Data la grammatica G = ({a}, {S, I, F, M}, P, S) con produzioni P

S -> a | aa | IaF
aF -> Maa | MaaF
aM -> Maa
IM -> Ia | aa

provare che genera il linguaggio {a2n | n >= 0}
---------------------------------------------------------------------------------------------------

Qualcuno ha provato a fare questo esercizio?
« Last Edit: 17-11-2017, 23:55:43 by ɹǝǝuıƃuǝsɹǝʌǝɹ » Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 2.776



WWW
« Reply #1 on: 16-11-2017, 22:47:36 »

Lasciate perdere.
E' troppo complesso.

Fate gli altri esercizi.
Logged
giorgio_buzzanca
Matricola
*
Online Online

Gender: Male
Posts: 11



« Reply #2 on: 17-11-2017, 09:38:43 »

Professore io credo comunque che ci sia un errore nel testo, perché con una grammatica del genere posso ritrovarmi stringhe costituite da caratteri non terminali a cui non posso applicare ulteriori regole di produzione, e mi riferisco in particolare alla regola di produzione IM --> Ia | aa. Questo perché non è presente una regola di produzione per Ia. Inoltre credo che anche la regola di produzione aM --> Maa sia problematica, perché non ci permettere di giungere ad una stringa composta da soli terminali quando dovrebbe essere così. Potrei sbagliarmi però, magari non ho capito/analizzato bene le regole di produzione.
Logged

Indirizzo email: giorgiobuzzanca@outlook.it
Public Key Id: 68BB499B
Public Key Fingerprint: FD792C4AAC7067DEDE54B070040F6AF568BB499B
Chiave su keyserver.pgp.com e pgp.mit.edu.
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 2.776



WWW
« Reply #3 on: 17-11-2017, 09:56:55 »

Professore io credo comunque che ci sia un errore nel testo, perché con una grammatica del genere posso ritrovarmi stringhe costituite da caratteri non terminali a cui non posso applicare ulteriori regole di produzione, e mi riferisco in particolare alla regola di produzione IM --> Ia | aa. Questo perché non è presente una regola di produzione per Ia. Inoltre credo che anche la regola di produzione aM --> Maa sia problematica, perché non ci permettere di giungere ad una stringa composta da soli terminali quando dovrebbe essere così. Potrei sbagliarmi però, magari non ho capito/analizzato bene le regole di produzione.

Ho sempre avuto tale sospetto pure io,
ma non ho mai avuto la voglia di mettermi a controllare con precisione....
Logged
josura
Matricola
*
Online Online

Gender: Male
Posts: 16


Ho paura.


« Reply #4 on: 17-11-2017, 10:39:43 »

Professore io credo comunque che ci sia un errore nel testo, perché con una grammatica del genere posso ritrovarmi stringhe costituite da caratteri non terminali a cui non posso applicare ulteriori regole di produzione, e mi riferisco in particolare alla regola di produzione IM --> Ia | aa. Questo perché non è presente una regola di produzione per Ia. Inoltre credo che anche la regola di produzione aM --> Maa sia problematica, perché non ci permettere di giungere ad una stringa composta da soli terminali quando dovrebbe essere così. Potrei sbagliarmi però, magari non ho capito/analizzato bene le regole di produzione.
Sono d'accordo con il mio collega, per esempio :
IaF--> IMaaF--> IMaMaa-->aaaMaa-->aaMaaaa-->aMaaaaaa-->Maaaaaaaa
dove M non ha nessuna regola di produzione che possa rendere la stringa composta di soli simboli terminali.
oppure :
IaF-->IMaa--> Iaaa
dove i simboli {a} sono 3, non so però se n siano numeri naturali o reali, poiché penso che se una grammatica genera il linguaggio {a^2^n | n >= 0} le stringhe generate dovrebberò essere del tipo{a,aa,aaaa,a^8,...}, per il resto, le altre stringhe che non contengono caratteri non terminali sono effettivamente formate da a^2^n simboli terminali:
per esempio:
IaF-->IMaa-->a4;
IaF--> IMaaF-->Ia3F-->Ia2Maa-->stesso procedimento di sopra, le a che stanno alla sinistra del simbolo non terminale M vengono raddoppiate-->IMa4aa-->a8;
IaF-->IMaaF-->IMaMaaF-->IaaMaaF-->...-->IMa12aa-->a16;
e così via...
Quindi è una grammatica che genera le stringhe a^2^n, con le sue eccezioni.
« Last Edit: 17-11-2017, 11:35:28 by josura » Logged

Prof. Barbanera non mi uccida, se proprio deve  lo faccia lentamente.
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 2.776



WWW
« Reply #5 on: 17-11-2017, 10:54:32 »

Sono d'accordo con il mio collega, per esempio :
IaF--> IMaaF--> IMaMaa-->aaaMaa-->aaMaaaa-->aMaaaaaa-->Maaaaaaaa
dove M non ha nessuna regola di produzione che possa rendere la stringa composta di soli simboli terminali.


Questo non dimostra nulla.
Non e' mica obbligatorio che una grammatica che definisce un linguaggio
sia tale che tutte le derivazioni portino a stringhe ti terminali...
Logged
josura
Matricola
*
Online Online

Gender: Male
Posts: 16


Ho paura.


« Reply #6 on: 17-11-2017, 11:47:28 »

Prof ho riscritto il mio post prima di leggerla, capisco che cosa intende, si potrebbe migliorare la grammatica in modo tale che tutte le derivazioni portino a stringhe di caratteri terminali, magari inserendo nell'alfabeto ε ed aggiungendo delle regole di produzione ,o mi sto allontanando troppo dalla consegna?
Logged

Prof. Barbanera non mi uccida, se proprio deve  lo faccia lentamente.
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 2.776



WWW
« Reply #7 on: 17-11-2017, 15:27:32 »

Prof ho riscritto il mio post prima di leggerla, capisco che cosa intende, si potrebbe migliorare la grammatica in modo tale che tutte le derivazioni portino a stringhe di caratteri terminali, magari inserendo nell'alfabeto ε ed aggiungendo delle regole di produzione ,o mi sto allontanando troppo dalla consegna?

Non ne vedo l'utilita'....
Logged
NuciforaNicolas
Matricola
*
Offline Offline

Posts: 5


« Reply #8 on: 17-11-2017, 21:23:36 »

facendo i calcoli, le uniche derivazioni che portano a delle stringhe formata da caratteri terminali sono:

S --> a (che può essere visto come a^2^0)

S --> aa (a^2^1)

s--> IaF --> IMaa --> aaaa (a^2^2)

Non sono riuscito a formare altre stringhe senza caratteri non terminali.

Questa è la mia idea, ma credo che non centri nulla
Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 2.776



WWW
« Reply #9 on: 18-11-2017, 12:26:46 »

Come dicevo,
o e' sbagliato, o e' troppo difficile.

Avete gia' fatto tutti gli altri esercizi sulle grammatiche, che vi intestardite con questo???
Logged
Pages: [1]   Go Up
Print
Jump to: