[Teoria] Automa deterministico

[ZfreS]

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?

[apatriarca]

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).

[ZfreS]

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.

[apatriarca]

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.

[ZfreS]

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.

[apatriarca]

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.

[ZfreS]

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?

[apatriarca]

Dove la stringa vuota non è permessa?

[ZfreS]

Intendo dire che se $w_0 = epsilon$ oppure $w_1=epsilon$ allora $w$ non è valida

[apatriarca]

Hai che \(w_0, w_1 \in \Sigma^*\) per cui non vedo perché le stringe vuote non dovrebbero essere valide.