Quesiti linguaggi formali

[mikoile]

Buonasera, vorrei deste uno sguardo a delle risposte che avrei dato a dei quesiti riguardanti i linguaggi formali e che riusciate a chiarire alcuni miei dubbi:

Determinare la composizione sincrona dei seguenti linguaggi:
1)
Risposta:

Dubbio: sono indeciso sulla c in quanto nella composizione sincrona le parole devono appartenere ad entrambi i linguaggi contemporaneamente , per cui non essendoci c in L2 sono indeciso se inserirla o meno.

2)

Risposta:

Essendo i due alfabeti uguali la composizione sincrona coincide con l'intersezione, quindi dovrei considerare gli elementi comuni dei due linguaggi:


3)
Risposta:

Il mio dubbio è se devo inserire '' o al suo posto '', quindi se degli elementi comuni considerare il massimo o il minim.

4)
Risposta:


5) calcolare la concatenazione dei due seguenti linguaggi:

Risposta:


Spero riusciate a risolvere i miei dubbi e che le restanti risposte siano giuste, grazie mille !

[Ianero]

Forse rugweri è l'unico che ti sa rispondere

[rugweri]

Presente

Intanto, cerchiamo di capire una cosa: cosa intendi per "composizione sincrona"? Purtroppo la terminologia di questo campo è estremamente difforme, per cui autori diversi identificano le cose in modo diverso. Sarebbe molto utile, a tal proposito, anche sapere dove hai preso i quesiti.
Per come la intendo io, la composizione sincrona equivale a mettere in parallelo gli automi dei due linguaggi, che praticamente vuol dire farne il prodotto cartesiano (ed è peraltro quello che si fa nell'equivalence checking dei circuiti sequenziali... ma non divaghiamo ), ma dalle risposte che dai ai quesiti immagino che tu intenda tutt'altro.

EDIT: nel frattempo, ti dico che il quinto esercizio (che non riguarda la composizione sincrona, quindi possiamo valutare subito) è corretto.

[fairyvilje]

Intanto, cerchiamo di capire una cosa: cosa intendi per "composizione sincrona"?.

Precisamente :/. Io questa roba l'ho pure studiata ma composizione sincrona? È la prima volta che sento questa terminologia . Ho provato anche a cercare in inglese online ma non ho trovato niente. In italiano c'è questo dove viene usata per costruire altre composizioni: http://home.deib.polimi.it/ferrarin/sup ... compo2.pdf
Insomma non mi sembra una terminologia molto da informatici puri :/.

[mikoile]

Buongiorno, per composizione sincrona (o concorrente) intendo :

[rugweri]

Immagino che siano gli appunti del Politecnico di Bari che girano in rete... cosa che avresti dovuto dirmi tu, visto che te l'avevo chiesto.

In ogni caso, quella definizione non è nemmeno coerente con l'esempio che la segue: perché nel linguaggio composto non sono incluse le concatenazioni, visto che esse sono ovviamente parole di e inoltre proiettando una concatenazione su uno dei linguaggi di partenza si ottiene (ovviamente: la proiezione serve a questo!) una parola di quest'ultimo?

In sostanza, quest'operazione che viene proposta negli appunti mi sembra un tentativo sbagliato di riscrivere l'intersezione tra automi per aggirare un dettaglio molto spinoso ma in realtà molto importante, tant'è che testi seri come l'Hopcroft-Motwani-Ullman non solo non lo tacciono, ma addirittura lo evidenziano (dedicandogli in particolare, nel caso specifico dell'HMU, un approfondimento): la natura della funzione di transizione di un DFA.
Probabilmente ti hanno detto che un automa deterministico ammette necessariamente, dati uno stato e un simbolo d'ingresso, una e una sola transizione... e formalmente è vero, ma nulla ti impedisce di inserire nel tuo automa (ed è ciò che si fa quando si converte un NFA in un DFA) uno stato "morto" dove andare a piantare il tuo automa quando un certo simbolo non lo vuoi accettare, e dunque rispettare la definizione di automa deterministico ammettendo però l'esistenza nell'alfabeto di simboli che in certi casi non causano una transizione "valida". Questa costruzione, per la cronaca, è sempre corretta, perché non modifica il linguaggio riconosciuto dall'automa.
Perché ti racconto questa roba? È presto detto: stando così le cose, possiamo definire l'intersezione tra automi in una forma semplice (e peraltro coerente con il teorema di Myhill-Nerode, se ti interessa e sai di che si tratta): dati due automi e , possiamo senz'altro sostituire i rispettivi alfabeti con avendo cura di aggiornare le funzioni di transizione in modo che possano portare ad un apposito stato di non accettazione quando necessario, e dunque ritrovarci a trattare l'intersezione tra gli automi e , che banalmente è questa cosa qui:

inter.png (9.91 KiB) Osservato 8762 volte

Ovvero è l'automa , che come puoi verificare riconosce esattamente le stringhe che vengono riconosciute da entrambi gli automi componenti.

Dato tutto ciò, ti faccio notare un altro dettaglio: la tua operazione viene fatta corrispondere all'intersezione nel caso in cui i due automi abbiano lo stesso alfabeto... ma come credo tu abbia visto leggendo le mie parole (che corrispondono esattamente a quelle che puoi trovare, meglio articolate e accompagnate da dimostrazioni rigorose e immagini, nel già citato HMU o in qualsiasi testo di teoria algebrica degli automi), puoi sempre porre che i due automi abbiano lo stesso alfabeto.

[mikoile]

Ah ecco . Esistono quindi delle fonti in cui il concetto viene esposto meglio e magari anche con esempi chiari ?
Per quanto riguarda i quesiti sopracitati come dovrei comportarmi ?

[rugweri]

Vedi, non è questione di "esporre meglio": quella roba lì è semplicemente sbagliata.
Comunque, il mio consiglio è di studiare bene l'Hopcroft-Motwani-Ullman, che ti ho proposto sopra: i primi quattro capitoli trattano i linguaggi regolari, che sono l'argomento di tuo interesse. Fatto questo, puoi svolgere gli esercizi in modo coerente.
Nota in questo senso un dettaglio importante a proposito della tua risposta al primo esercizio: la parola "dab" non appartiene a nessuno dei due linguaggi componenti.

[mikoile]

Grazie mille !