[Teoria] Automa deterministico

[ZfreS]

Si, in effetti è così. Ma rimane questo problema:
potrei avere la stringa $w=0110$ che potrebbe essere vista in due modi: $w_0=epsilon$ $x=1$ $y=1$ $w_1=0$ oppure come $w_1=0$ $x=1$ $y=1$ $w_1=0$. Mel primo caso dovrebbe essere accettata, nel secondo no. Come distinguere i due casi nell'automa?

[apatriarca]

Non lo fai. La condizione è equivalente a chiedere che ogni coppia di simboli adiacenti è diversa.

[ZfreS]

Vediamo se funziona questo schema:
da q0 leggo 0 vado nello stato q1
da q0 leggo 1 vado nello stato q2
da q1 leggo 0 vado nello stato q0
da q1 leggo 1 vado nello stato q3
da q2 leggo 1 vado nello stato q0
da q2 leggo 0 vado nello stato q4
gli stati q3 e q4 possono essere acettanti oppure
da q3 leggo 0 e termino oppure vado in q5 e termino oppure torno in q3
da q2 leggo 1 e termino oppure vado in q4 e termino oppure torno in q2

Pensandoci anche gli stati q1 e q2 dovrebbero essere accettanti.

[apatriarca]

Il tuo automa riconosce qualcosa come 0001 che non è certamente valido in base al tuo linguaggio. Inoltre credo il linguaggio contenga anche tutte le parole di lunghezza 0 e 1, ma potrei sbagliarmi

[ZfreS]

Scusa ma ancora non ho risolto. Per esempio, se la parola fosse $w = 00$ in cui $w_0=epsilon$ $w_1=epsilon$ $x =0$ $y=0$ la parola non deve essere accettata essendo $x=y$, ma se la parola fosse $w=0010$ in cui $w_0=00$ $w_1=epsilon$ $x=1$ $y=0$ la parola è corretta e deve essere riconosciuta. Ma in entrambi i casi l'automa vede all'inzio $00$, come fa a a distinguere la correttezza delle due parole?

[apatriarca]

Il secondo esempio non va accettato. La condizione deve valere per ogni scelta di $w_0$ e $w_1$. Non è sufficiente che sia valida per una particolare condizione.

[ZfreS]

Non capisco, nella seconda parola è stat fatta una delle tante possibili scelte per $w_0$ e $w_1$

[apatriarca]

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.

[ZfreS]

Ti ringrazio per la risposta esaustiva, finalmente ho capito. In pratica, la decomposizione $w = w_0xyw_1$ deve poter "acchiappare" tutte le stringhe che si scrivono in quel modo ma che risulti $x!=y$. Nell'esempio del post precedente la parola $w=0010$ può anche essere interpretata oltre alla maniera da me descritta, anche come $w_0 = epsilon$ $x=0$ $y= 0$ e $w_1=10$ che rende falsa l'implicazione. Quindi l'unico modo affinhè valgano entrambe è che simboli adiacenti devono essere diversi tra loro.

[apatriarca]

Esatto