Automi deterministici e non

[JoKeRxbLaCk93]

Ciao a tutti, come posso risolvere questo esercizio? E' pura teoria

Si dia la definizione formale, in simboli, di linguaggio riconosciuto da un automa a stati finiti non deterministico, esplicitando il significato di ogni simbolo usato.

Allora, io ho una automa \( M = (A, Q, \tau , F, q_{0}) \) dove $A$ = alfabeto, $Q$ = inisieme degli stati, $\tau$ = stati di transizione, $F$ = insieme degli stati finali, $q_{0}$ = stato iniziale.
Gli stati di transizione variano secondo: \( \tau = A\times Q \rightarrow P(Q) \).

Da definizione, un automa a stati finiti non è deterministico quando, per ogni stato, viene applicato un insieme di possibili transizioni.

Il linguaggio riconosciuto da un automa a stati finiti non deterministico è il seguente:
$L(G) = {alpha in A^{\star} | q_{0}alpha \rightarrow^{\star}Mq_{f}, q_{f} in F}$
E' corretto?

[onlyReferee]

Ciao
Allora, $\tau$ è la funzione di transizione, non l'insieme degli stati di transizione.
Poi, la definizione di automa non deterministico scritta così non è corretta. Il fatto che per ogni stato venga applicato un insieme di possibili transizioni in realtà avviene in ogni automa. Una definizione potrebbe essere: un automa non è deterministico se $\tau$ non soddisfa più il requisito di essere funzione, ossia: $$\exists u \in A, q_i, q_j, q_k \in Q (j \ne k) | \tau(u, q_i) = q_j \land \tau(u, q_i) = q_k.$$

[JoKeRxbLaCk93]

"onlyReferee":Ciao
Allora, $\tau$ è la funzione di transizione, non l'insieme degli stati di transizione.
Poi, la definizione di automa non deterministico scritta così non è corretta. Il fatto che per ogni stato venga applicato un insieme di possibili transizioni in realtà avviene in ogni automa. Una definizione potrebbe essere: un automa non è deterministico se $\tau$ non soddisfa più il requisito di essere funzione, ossia: $$\exists u \in A, q_i, q_j, q_k \in Q (j \ne k) | \tau(u, q_i) = q_j \land \tau(u, q_i) = q_k.$$

Ok, perfetto, grazie mille!