Cos'è ElectroYou | Login Iscriviti

ElectroYou - la comunità dei professionisti del mondo elettrico

Quesiti linguaggi formali

PLC, servomotori, inverter...robot

Moderatori: Foto Utentecarlomariamanenti, Foto Utentedimaios

0
voti

[1] Quesiti linguaggi formali

Messaggioda Foto Utentemikoile » 6 lug 2019, 18:48

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) L1=(ab,c) \quad  L2=(a,da)
Risposta:
L1||L2=(ab,dab,c)
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)
L1=(a,ab^{n}a,c \quad n=0,1..) \quad L2=(b^{n}a^{m},c  \quad n,m=0,1..)
Risposta:
L1||L2=L1 \cap L2=(c,a,a^{2}b^{n}  \quad n=0,1,..)
Essendo i due alfabeti uguali la composizione sincrona coincide con l'intersezione, quindi dovrei considerare gli elementi comuni dei due linguaggi:


3)L1=(a^{k}b^{h} \quad h,k=0,1..) \quad L2=(c^{k}a, ac \quad k=0,1,..)
Risposta:
L1||L2=(c^{k}a^{m}b^{h}, a^{k}c \quad h,k,m=0,1,..)
Il mio dubbio è se devo inserire 'a^{k}' o al suo posto 'a', quindi se degli elementi comuni considerare il massimo o il minim.

4)L1=(\epsilon, ab^{k},ab^{k}c \quad k=0,1) \quad L2=(d^{k}bc \quad k=0,1..)
Risposta:
L1||L2=(\epsilon,d^{k}b^{k}c,ab^{k})

5) calcolare la concatenazione dei due seguenti linguaggi:
L1=(\epsilon, ab^{k},ab^{k}c \quad k=0,1,..) \quad L2=(d^{k}bc \quad k=0,1,..)
Risposta:
L1L2=(d^{k}bc,ab^{k}d^{h}bc, ab^{k}cd^{h}bc \quad h,k=0,1,...)

Spero riusciate a risolvere i miei dubbi e che le restanti risposte siano giuste, grazie mille !
Avatar utente
Foto Utentemikoile
15 4
 
Messaggi: 39
Iscritto il: 3 feb 2018, 13:01

0
voti

[2] Re: Quesiti linguaggi formali

Messaggioda Foto UtenteIanero » 6 lug 2019, 19:46

Forse Foto Utentewruggeri è l'unico che ti sa rispondere :-)
Servo, dai a costui una moneta, perché ha bisogno di trarre guadagno da ciò che impara.
Euclide.
Avatar utente
Foto UtenteIanero
7.319 5 8 13
Master EY
Master EY
 
Messaggi: 3773
Iscritto il: 21 mar 2012, 15:47

0
voti

[3] Re: Quesiti linguaggi formali

Messaggioda Foto Utentewruggeri » 6 lug 2019, 20:20

Presente :mrgreen:

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 :mrgreen: ), 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.
Rispondo solo a chi si esprime correttamente in italiano.
Se non conosci un argomento, non parlarne.
Gli unici fatti sono quelli dimostrabili, il resto è opinione.
Non dirò una parola sulla politica e sul M5S, del quale aspetto solo l'estinzione.
Avatar utente
Foto Utentewruggeri
4.975 1 8 13
Master EY
Master EY
 
Messaggi: 970
Iscritto il: 25 nov 2016, 18:46

1
voti

[4] Re: Quesiti linguaggi formali

Messaggioda Foto Utentefairyvilje » 6 lug 2019, 23:42

wruggeri ha scritto: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 :mrgreen: . 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 :/.
"640K ought to be enough for anybody" Bill Gates (?) 1981
Qualcosa non ha funzionato...

Lo sapete che l'arroganza in informatica si misura in nanodijkstra? :D
Avatar utente
Foto Utentefairyvilje
11,4k 4 9 12
G.Master EY
G.Master EY
 
Messaggi: 2452
Iscritto il: 24 gen 2012, 19:23

0
voti

[5] Re: Quesiti linguaggi formali

Messaggioda Foto Utentemikoile » 7 lug 2019, 9:26

Buongiorno, per composizione sincrona (o concorrente) intendo :
Allegati
Schermata 2019-07-07 alle 09.21.44.png
Avatar utente
Foto Utentemikoile
15 4
 
Messaggi: 39
Iscritto il: 3 feb 2018, 13:01

5
voti

[6] Re: Quesiti linguaggi formali

Messaggioda Foto Utentewruggeri » 7 lug 2019, 9:57

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^* 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 \mathcal{M}_1 = (X_1, Q_1, q_{0, 1}, F_1, \delta_1) e \mathcal{M}_2 = (X_2, Q_2, q_{0, 2}, F_2, \delta_2), possiamo senz'altro sostituire i rispettivi alfabeti con X = X_1 \cup X_2 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 \mathcal{M}_1 = (X, Q_1, q_{0, 1}, F_1, \delta_1) e \mathcal{M}_2 = (X, Q_2, q_{0, 2}, F_2, \delta_2), che banalmente è questa cosa qui:
inter.png
inter.png (9.91 KiB) Osservato 717 volte

Ovvero è l'automa \mathcal{M} = (X, Q_1 \times Q_2, (q_{0, 1}, q_{0, 2}), F_1 \times F_2, (\delta_1, \delta_2), 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.
Rispondo solo a chi si esprime correttamente in italiano.
Se non conosci un argomento, non parlarne.
Gli unici fatti sono quelli dimostrabili, il resto è opinione.
Non dirò una parola sulla politica e sul M5S, del quale aspetto solo l'estinzione.
Avatar utente
Foto Utentewruggeri
4.975 1 8 13
Master EY
Master EY
 
Messaggi: 970
Iscritto il: 25 nov 2016, 18:46

0
voti

[7] Re: Quesiti linguaggi formali

Messaggioda Foto Utentemikoile » 7 lug 2019, 11:13

Ah ecco #-o . 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 ?
Avatar utente
Foto Utentemikoile
15 4
 
Messaggi: 39
Iscritto il: 3 feb 2018, 13:01

1
voti

[8] Re: Quesiti linguaggi formali

Messaggioda Foto Utentewruggeri » 7 lug 2019, 11:38

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.
Rispondo solo a chi si esprime correttamente in italiano.
Se non conosci un argomento, non parlarne.
Gli unici fatti sono quelli dimostrabili, il resto è opinione.
Non dirò una parola sulla politica e sul M5S, del quale aspetto solo l'estinzione.
Avatar utente
Foto Utentewruggeri
4.975 1 8 13
Master EY
Master EY
 
Messaggi: 970
Iscritto il: 25 nov 2016, 18:46

0
voti

[9] Re: Quesiti linguaggi formali

Messaggioda Foto Utentemikoile » 7 lug 2019, 12:05

Grazie mille !
Avatar utente
Foto Utentemikoile
15 4
 
Messaggi: 39
Iscritto il: 3 feb 2018, 13:01


Torna a Automazione industriale ed azionamenti

Chi c’è in linea

Visitano il forum: Nessuno e 0 ospiti