[Teoria] Automa deterministico
Buongiorno. Devo rappresentare un'automa a stati finiti deterministico che riconosca il seguente linguaggio:
$L = {winSigma^**|AAx,yinSigma^^w_0,w_1inSigma^**| w=w_0xyw_1 => x!=y}$
Il problema è che mi viene difficile capire come gestire i vari stati. Qualcuno avrebbe un'intuizione da suggerire?
$L = {winSigma^**|AAx,yinSigma^^w_0,w_1inSigma^**| w=w_0xyw_1 => x!=y}$
Il problema è che mi viene difficile capire come gestire i vari stati. Qualcuno avrebbe un'intuizione da suggerire?
Risposte
Sono un po' arrugginito con queste cose, ma credo che il linguaggio richieda semplicemente che simboli successivi siano diversi tra di loro. Creerei quindi un automa con uno stato per ogni simbolo dell'alfabeto più stati per l'inizio e fine stringa. Ogni stato è quindi connesso a ogni altro stato tranne se stesso e l'inizio della stringa (credo che la condizione per il passaggio sia chiara).
Da come l'ho interpretata, bisognerebbe garantire che i due simboli consecutivi x e y siano diversi. Ciò che non capisco è come l'antecedente dell'implicazione possa essere falso. Capito questo basterebbe verificare che se l'antecedente è falso ma x e y sono uguali, la stringa viene rifitutata, in tutti gli altri casi accettata.
Siccome w0 e w1 sono stringhe di lunghezza qualsiasi, eventualmente vuote, allora x e y sono due simboli qualsiasi consecutivi della stringa w. L'ultima condizione richiede quindi siano diversi. L'antecedente è falso per stringhe di lunghezza minore di 2 per cui non esiste una tale scrittura.
Il fatto è che io non so all'inizio se w0 è vuota, per cui se trovo due simboli consecutivi uguali, non so se facciano parte di w0 oppure siano x e y. Questo introduce indeterminismo, al contrario di ciò che vuole l'esercizio. pensare l'automa in senso deterministico rende tutto più difficile.
Stai interpretando la condizione nel modo sbagliato. Supponiamo di avere \(w = abed\). Esistono diversi modi di scrivere \(w = w_0xyw_1\) e per ognuno di essi deve valere la condizione. Infatti hai le seguente possibilità:
\[
\begin{align*}
&w_0 = \epsilon, &x = a, \quad &y = b, &w_1 = ed \\
&w_0 = a, &x = b, \quad &y = e, &w_1 = d \\
&w_0 = ab, &x = e, \quad &y = d, &w_1 = \epsilon
\end{align*}
\]
Questa stringa rispetta la condizione perché ogni simbolo è diverso da quello che lo precede e segue.
\[
\begin{align*}
&w_0 = \epsilon, &x = a, \quad &y = b, &w_1 = ed \\
&w_0 = a, &x = b, \quad &y = e, &w_1 = d \\
&w_0 = ab, &x = e, \quad &y = d, &w_1 = \epsilon
\end{align*}
\]
Questa stringa rispetta la condizione perché ogni simbolo è diverso da quello che lo precede e segue.
Ma anche la stringa $aab$ in cui $w_0=epsilon$ $x=a$ $y=a$ $w_1=b$ deve essere accettata. Da quel che ho capito la stringa vuota non è permessa, quindi la stringa sopra non è valida come $w$ da cui l'antecedente è falso ma pure il conseguente perchè $x=y$, tuttavia l'implicazione è sempre vera, o sbaglio?
Dove la stringa vuota non è permessa?
Intendo dire che se $w_0 = epsilon$ oppure $w_1=epsilon$ allora $w$ non è valida
Hai che \(w_0, w_1 \in \Sigma^*\) per cui non vedo perché le stringe vuote non dovrebbero essere valide.
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?
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?
Non lo fai. La condizione è equivalente a chiedere che ogni coppia di simboli adiacenti è diversa.
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.
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.
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
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?
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.
Non capisco, nella seconda parola è stat fatta una delle tante possibili scelte per $w_0$ e $w_1$
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 [tt](0(10)*1? | 1(01)*0)?[/tt]
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.
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 [tt](0(10)*1? | 1(01)*0)?[/tt]
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.
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.
Esatto
Perfetto, grazie ancora per la pazienza!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo