da apatriarca » 03/10/2022, 11:41
La mia impressione è che il tuo problema non sia tanto nella conversione all'automa deterministico, ma nel comprendere come sia fatto il linguaggio.
Il linguaggio è formato da tutte le stringhe \(w \in \Sigma^*\) per cui la condizione dopo la barra verticale \(\mid\) è soddisfatta. La condizione è abbastanza complicata per cui consideriamo una parte per volta.
\[ \forall\;x, y \in \Sigma \wedge \forall\;w_0, w_1 \in \Sigma^* \]
Questa prima parte ci dice di considerare TUTTE le possibili stringhe \(w_0\) e \(w_1\) e tutti i possibili caratteri \(x\) e \(y\). La condizione su \(w\) deve essere verificata per OGNI scelta di queste variabili.
\[ w = w_0\,x\,y\,w_1 \implies x \neq y \]
Questa seconda parte ci dice che possiamo ignorare ogni scelta di \(x, y, w_0, w_1\) fatta al punto precedente se \(w \neq w_0\,x\,y\,w_1\). In tal caso la condizione sarà infatti sempre vera. Se invece abbiamo che \(w = w_0\,x\,y\,w_1\) allora è necessario verificare che \(x \neq y\). Devi quindi considerare TUTTE le possibili decomposizioni di \(w\) in \(x, y, w_0, w_1\) e verificare questa condizione.
Vediamo qualche esempio con \(\Sigma = \{0, 1\}\).
\(w \in \{ \epsilon, 0, 1 \}\). In questo caso hai che NON ESISTONO DECOMPOSIZIONI di \(w\) in \(x, y, w_0, w_1\) e quindi la condizione è VERIFICATA. Queste stringhe appartengono al linguaggio.
\(\exists a, b \in \Sigma, w = a\,b\). In tal caso abbiamo che \(w_0 = w_1 = \epsilon\), \(x = a\), \(y = b\) è l'unica decomposizione. Perché la stringa appartenga al linguaggio dobbiamo quindi avere \(a \neq b\).
\(\exists a, b, c \in \Sigma, w = a\,b\,c\). Qui abbiamo due decomposizioni. \(w_0 = a, x = b, y = c, w_1 = \epsilon\) e \(w_0 = \epsilon, x = a, y = b, w_1 = c\). La condizione è quindi equivalente a richiedere che \(a \neq b \wedge b \neq c\).
Usando lo stesso ragionamento dell'ultimo esempio vediamo che se \(c_i\) e il carattere \(i\)-esimo della stringa \(w\), la condizione è equivalente a richiedere che \(\forall i, c_i \neq c_{i+1}\).
Le prime stringhe del linguaggio sono quindi della forma \(\epsilon, 0, 1, 01, 10, 010, 101, 0101, 1010, \dots\). Volendo scrivere il linguaggio come una espressione regolare potrei avere qualcosa come (0(10)*1? | 1(01)*0)?
L'automa deterministico è a mio parere più semplice da scrivere. Dovrai avere uno stato \(S\) iniziale che è anche accettante. Avrai quindi stati \(Q_0\) e \(Q_1\) anche loro accettanti e transizioni \(S \to_0 Q_0\) se incontri lo zero e \(S \to_1 Q_1\) se incontri l'uno. Hai quindi transizioni \(Q_0 \to_1 Q_1\) se incontri un uno e \(Q_1 \to_0 Q_0\) se incontri uno zero. Hai infine uno stato di errore \(E\), l'unico non accettante. In questo caso hai transizioni \(Q_0 \to_0 E\) e \(Q_1 \to_1 E\) in caso incontri rispettivamente lo zero e l'uno. Hai quindi infine la transizione \(E \to_{0, 1} E\) indipendente dall'input.