Pages: [1]   Go Down
Print
Author Topic: Esercizio 22 - Linguaggi Formali  (Read 389 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Sain
Matricola
*
Offline Offline

Gender: Male
Posts: 25



« on: 10-10-2018, 14:42:22 »

Nella pagina degli esercizi sui linguaggi formali mi sono soffermato sull'esercizio 22, il quale chiede:

Dimostrare che per ogni possibile k il linguaggio
{anbn| n ≤k}
e' regolare.

Mi chedo però se è davvero un linguaggio regolare. Se fosse regolare, fissando un k qualsiasi dovrebbe esistere una grammatica REGOLARE che lo generi. Ma questo non sono riuscito a provarlo, quindi di conseguenza il linguaggio dato non è regolare.
Dico bene oppure esiste una grammatica che lo genera e quindi il linguaggio è regolare?
Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 3.027



WWW
« Reply #1 on: 10-10-2018, 20:58:42 »

Mi chedo però se è davvero un linguaggio regolare. Se fosse regolare, fissando un k qualsiasi dovrebbe esistere una grammatica REGOLARE che lo generi. Ma questo non sono riuscito a provarlo, quindi di conseguenza il linguaggio dato non è regolare.

Siccome tu non sei riuscito a dimostrare che non e' regolare allora non lo e'?
Non metto in dubbio le tue capacita', ma affermare
"questa cosa non e' possibile perche' io non ci riesco (e quindi nessun altro al mondo potrebbe)"
mi pare un tantinello immodesto.

Comunque, prova, anziche' cercare una grammatica regolare, a cercare una espressione regolare.
Forse in questo modo ce la fai.

FB
Logged
Sain
Matricola
*
Offline Offline

Gender: Male
Posts: 25



« Reply #2 on: 11-10-2018, 15:16:30 »

Va bene, allora provo a scrivere una grammatica regolare G e un'espressione regolare che penso possano generare il linguaggio.

La grammatica regolare che mi viene in mente è:

G = ({a,b}, {S, A}, P, S)

con regole di produzione:

S->aS|A|a
A->bA|b
______________________________________________________________

Mentre, l'espressione regolare che propongo è:

a*b*
______________________________________________________________

Vanno bene per generare il linguaggio?
Logged
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.472


Più grande è la lotta, e più è glorioso il trionfo


WWW
« Reply #3 on: 12-10-2018, 08:28:56 »

Va bene, allora provo a scrivere una grammatica regolare G e un'espressione regolare che penso possano generare il linguaggio.

La grammatica regolare che mi viene in mente è:

G = ({a,b}, {S, A}, P, S)

con regole di produzione:

S->aS|A|a
A->bA|b
______________________________________________________________

Mentre, l'espressione regolare che propongo è:

a*b*
______________________________________________________________

Vanno bene per generare il linguaggio?
Ragazzo, per quanto k sia fissato (cioè una costante), è a te ignoto.
Questo significa che, se tale k ha realmente importanza nella descrizione del linguaggio (e ne ha), la tua espressione regolare/automa/grammatica regolare dovrà necessariamente far "comparire" qualcosa che ha a che fare con quel k.

Siccome k è un limitatore per il secondo operando dell'operazione di "elevazione a potenza" rispetto a una parola (con forte abuso di terminologia, ok), e l'"elevazione a potenza" descrive una quantità di lettere, non mi stupirei che tale k denotasse, nella tua espressione regolare/automa/grammatica regolare, una scrittura del tipo 1, 2, ... k (volte?) qualcosa.

Questo significa, che per ogni k fissato, esiste una espressione regolare/automa/grammatica regolare la cui rappresentazione è funzione di k (non è necesariamente sempre lo stesso cioè).
Logged

La grande marcia della distruzione mentale proseguirà. Tutto verrà negato. Tutto diventerà un credo. È un atteggiamento ragionevole negare l'esistenza delle pietre sulla strada; sarà un dogma religioso affermarla. È una tesi razionale pensare di vivere tutti in un sogno; sarà un esempio di saggezza mistica affermare che siamo tutti svegli. Accenderemo fuochi per testimoniare che due più due fa quattro. Sguaineremo spade per dimostrare che le foglie sono verdi in estate. Non ci resterà quindi che difendere non solo le incredibili virtù e saggezze della vita umana, ma qualcosa di ancora più incredibile: questo immenso, impossibile universo che ci guarda dritto negli occhi. Combatteremo per i prodigi visibili come se fossero invisibili. Guarderemo l'erba e i cieli impossibili con uno strano coraggio. Saremo tra coloro che hanno visto eppure hanno creduto.

In tutto, amare e servire.

  
                            ن                           
I can deal with ads,
I can deal with buffer,
but when ads buffer
I suffer...

...nutrimi, o Signore, "con il pane delle lacrime; dammi, nelle lacrime, copiosa bevanda...

   YouTube 9GAG    anobii  S  Steam T.B.o.I. Wiki [univ] Lezioni private  ʼ  Albo d'Ateneo Unicode 3.0.1
Usa "Search" prima di aprire un post - Scrivi sempre nella sezione giusta - Non spammare - Rispetta gli altri utenti - E ricorda di seguire il Regolamento
Sain
Matricola
*
Offline Offline

Gender: Male
Posts: 25



« Reply #4 on: 13-10-2018, 14:44:20 »

Ti ringrazio per l'esaustiva spiegazione. Penso di aver capito che: essendo che non è noto quanto valga n (di sicuro dipende da k, che denota il valore massimo che può assumere n), allora n (diciamo che informalmente) può assumere due valori diversi (oppure uguali) essendo che compare due volte come esponente di a e di b.

Per esempio: a2b5 = aabbbbb  (che è una stringa appartenente al linguaggio in questione).

Dico bene?
« Last Edit: 13-10-2018, 16:55:00 by Sain » Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 3.027



WWW
« Reply #5 on: 14-10-2018, 08:55:43 »

Reverse ti ha dato un ottimo suggerimento.


Quote
Per esempio: a2b5 = aabbbbb  (che è una stringa appartenente al linguaggio in questione).
Dico bene?

No.
Le stringhe devono avere la forma anbn dove n e' un qualsiasi numero minore di k.
Nota pero' che n "eleva a potenza" sia a che b,
quindi la tua stringa non appartiene al linguaggio (peraltro non hai specificato neanche quale k hai preso in considerazione).

Una domanda:
risulti registrato al Forum da Maggio. Immagino tu sia iscritto al secondo anno.
Hai seguito (o dato) matematica discreta?

FB
« Last Edit: 14-10-2018, 08:58:44 by Franco Barbanera » Logged
Sain
Matricola
*
Offline Offline

Gender: Male
Posts: 25



« Reply #6 on: 14-10-2018, 15:51:12 »

Le stringhe devono avere la forma anbn dove n e' un qualsiasi numero minore di k.

Quindi n può assumere tutti i valori minori o uguali a k?
Se fosse così, fissando k, per esempio k=3, potrei dedurre che le stringhe appartenenti al linguaggio {anbn | n≤3} sono: {ε, ab, aabb, aaabbb}. E' un'interpretazione corretta? testate Scusate se sto impiegando così tanto tempo per capire qualcosa che può sembrare banale che però è estremamente importante.
Grazie per i suggerimenti! pray

Comunque si, sono iscritto al secondo anno e ho dato matematica discreta.

Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 3.027



WWW
« Reply #7 on: 14-10-2018, 19:49:10 »

Le stringhe devono avere la forma anbn dove n e' un qualsiasi numero minore di k.

Quindi n può assumere tutti i valori minori o uguali a k?
Se fosse così, fissando k, per esempio k=3, potrei dedurre che le stringhe appartenenti al linguaggio {anbn | n≤3} sono: {ε, ab, aabb, aaabbb}. E' un'interpretazione corretta? testate Scusate se sto impiegando così tanto tempo per capire qualcosa che può sembrare banale che però è estremamente importante.
Grazie per i suggerimenti! pray

Giusto.
Quindi? Qual e' una espressione regolare che rappresenta quel linguaggio?...


Quote
Comunque si, sono iscritto al secondo anno e ho dato matematica discreta

Ah....
Approfitta dello studio del corso di Analisi per imparare a manipolare un po' meglio i concetti matematici.

Un caro saluto
FB


Logged
Sain
Matricola
*
Offline Offline

Gender: Male
Posts: 25



« Reply #8 on: 14-10-2018, 22:12:41 »

L'espressione regolare che avevo fornito in qualche messaggio fa (ovvero: a*b*) penso che non possa generare il linguaggio, perché può generare stringhe con un numero di a diverso da quello di b.
Quindi propongo questa espressione regolare (essendo noto che il linguaggio è {anbn | n≤3}):

ε+ab+aabb+aaabbb.

Penso però che sia una soluzione "macchinosa"... boh
E' comunque corretto scrivere una e.r. in questo modo?   
Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 3.027



WWW
« Reply #9 on: 15-10-2018, 14:17:32 »

L'espressione regolare che avevo fornito in qualche messaggio fa (ovvero: a*b*) penso che non possa generare il linguaggio, perché può generare stringhe con un numero di a diverso da quello di b.
Quindi propongo questa espressione regolare (essendo noto che il linguaggio è {anbn | n≤3}):

ε+ab+aabb+aaabbb.

Penso però che sia una soluzione "macchinosa"... boh
E' comunque corretto scrivere una e.r. in questo modo?   

Sara' macchinosa, ma e' l'unica possibile...   
Logged
Sain
Matricola
*
Offline Offline

Gender: Male
Posts: 25



« Reply #10 on: 15-10-2018, 17:34:52 »

Grazie tante prof!! Mi è stato molto d'aiuto. yoh
Logged
Pages: [1]   Go Up
Print
Jump to: