Espressione regolare

[sara09]

Buongiorno potete dirmi se tale automa corrisponde alla seguente espressione regolare che ho scritto in foto...allego la foto perché è impossibile da disegnare
Grazie in anticipo

[apatriarca]

Non è corretta. L'automa accetta per esempio la stringa ba, ma la tua espressione regolare non lo fa.

[sara09]

Non è corretta. L'automa accetta per esempio la stringa ba, ma la tua espressione regolare non lo fa.

Capito potrei correggerla così:
(a(b*(a(b*a))))(b(b*a))

[apatriarca]

No, continua a non essere esatto. Il problema è che puoi per esempio percorrere il percorso \(q_1 \to q_2 \to q_3 \to q_1\) più volte mentre nella tua espressione regolare ti fermi prima. Un modo per costruire la tua espressione regolare è quella di scrivere una equazione per ogni stato che rappresenta tutte le sue possibili transizioni in ingresso (l'\(\epsilon\) è presente perché \(q_1\) è lo stato iniziale):
\[
\begin{align*}
q_1 &= q_3\,a + \epsilon \\
q_2 &= q_1\,a + q_2\,b \\
q_3 &= q_1\,b + q_2\,a + q_3\,b
\end{align*}
\]
A questo punto c'è bisogno del teorema di Arden che ci dice che se \(P\) e \(Q\) sono due espressioni regolari e \(P\) non contiene \(\epsilon\), allora l'equazione \(R = Q + RP\) ha un'unica soluzione uguale a \( R = QP^* \). Con questo teorema possiamo quindi risolvere le equazioni nel seguente modo (l'obiettivo finale è trovare l'espressione per lo stato finale \(q_1\)):
\[
\begin{align*}
q_2 &= q_1\,a + q_2\,b \\
&= q_1\,a\,b^* \quad \text{(Teorema di Arden)} \\
q_3 &= q_1\,b + q_2\,a + q_3\,b \\
&= q_1\,b + (q_1\,a\,b^*)\,a + q_3\,b \quad \text{(Sostituzione di $q_2$)} \\
&= q_1\,(b + a\,b^*\,a) + q_3\,b \\
&= q_1\,(b + a\,b^*\,a)\,b^* \quad \text{(Teorema di Arden)} \\
q_1 &= q_3\,a + \epsilon \\
q_1 &= \epsilon + \bigl(q_1\,(b + a\,b^*\,a)\,b^*\bigr)\,a \\
&= \bigl((b + a\,b^*\,a)\,b^*\,a\bigr)^* \quad \text{(Teorema di Arden)}
\end{align*}
\]

[sara09]

No, continua a non essere esatto. Il problema è che puoi per esempio percorrere il percorso \(q_1 \to q_2 \to q_3 \to q_1\) più volte mentre nella tua espressione regolare ti fermi prima. Un modo per costruire la tua espressione regolare è quella di scrivere una equazione per ogni stato che rappresenta tutte le sue possibili transizioni in ingresso (l'\(\epsilon\) è presente perché \(q_1\) è lo stato iniziale):
\[
\begin{align*}
q_1 &= q_3\,a + \epsilon \\
q_2 &= q_1\,a + q_2\,b \\
q_3 &= q_1\,b + q_2\,a + q_3\,b
\end{align*}
\]
A questo punto c'è bisogno del teorema di Arden che ci dice che se \(P\) e \(Q\) sono due espressioni regolari e \(P\) non contiene \(\epsilon\), allora l'equazione \(R = Q + RP\) ha un'unica soluzione uguale a \( R = QP^* \). Con questo teorema possiamo quindi risolvere le equazioni nel seguente modo (l'obiettivo finale è trovare l'espressione per lo stato finale \(q_1\)):
\[
\begin{align*}
q_2 &= q_1\,a + q_2\,b \\
&= q_1\,a\,b^* \quad \text{(Teorema di Arden)} \\
q_3 &= q_1\,b + q_2\,a + q_3\,b \\
&= q_1\,b + (q_1\,a\,b^*)\,a + q_3\,b \quad \text{(Sostituzione di $q_2$)} \\
&= q_1\,(b + a\,b^*\,a) + q_3\,b \\
&= q_1\,(b + a\,b^*\,a)\,b^* \quad \text{(Teorema di Arden)} \\
q_1 &= q_3\,a + \epsilon \\
q_1 &= \epsilon + \bigl(q_1\,(b + a\,b^*\,a)\,b^*\bigr)\,a \\
&= \bigl((b + a\,b^*\,a)\,b^*\,a\bigr)^* \quad \text{(Teorema di Arden)}
\end{align*}
\]

Mi sa che parliamo di due cose diverse perche la tua soluzione tra le varie risposte non c’è...ti mando l’intero esercizi:

[apatriarca]

La notazione è leggermente diversa, ma stiamo dicendo la stessa cosa. Invece del \(+\) il tuo esercizio usa \(\cup\) e invece di concatenare usa \(\cdot\). Inoltre non usa il fatto che le operazioni sono associative (e quindi ci sono più parentesi del necessario). Inoltre \(\cup\) è commutativa per cui si possono scambiare i due argomenti della funzione. In altre parole la risposta corretta è la seconda.

[sara09]

La notazione è leggermente diversa, ma stiamo dicendo la stessa cosa. Invece del \(+\) il tuo esercizio usa \(\cup\) e invece di concatenare usa \(\cdot\). Inoltre non usa il fatto che le operazioni sono associative (e quindi ci sono più parentesi del necessario). Inoltre \(\cup\) è commutativa per cui si possono scambiare i due argomenti della funzione. In altre parole la risposta corretta è la seconda.

Ah grazie ed invece per quest’altro esercizio:


La giusta è la penultima?