Automa

[faby99s]

Sia
A={a,b}

Allora realizzare l’automa tale che:
L={w||w|>=1 e ogni lettera di w in posizione dispari è una a}
Esibire un automa finito che accetta L, io ho fatto così:


È giusto?

[apatriarca]

L'automa mi sembra corretto mentre non sono convinto dell'espressione regolare. Mi sembra per esempio accettare qualcosa come \(abb\) che non appartiene al linguaggio. Inoltre \(a\) è già incluso nella prima parte dell'espressione perché l'operatore \(\,^*\) accetta anche la stringa vuota. Qualcosa come la seguente credo dovrebbe funzionare:
\[ a \cdot \bigl((a \cup b) \cdot a \bigr)^* \cdot ( \epsilon \cup a \cup b ) \]

[faby99s]

"apatriarca":L'automa mi sembra corretto mentre non sono convinto dell'espressione regolare. Mi sembra per esempio accettare qualcosa come \(abb\) che non appartiene al linguaggio. Inoltre \(a\) è già incluso nella prima parte dell'espressione perché l'operatore \(\,^*\) accetta anche la stringa vuota. Qualcosa come la seguente credo dovrebbe funzionare:
\[ a \cdot \bigl((a \cup b) \cdot a \bigr)^* \cdot ( \epsilon \cup a \cup b ) \]

Ok la prima parte non sapevo che * accetta anche la parola vuota ma la seconda parte non riesco a capirla...potresti spiegarmela?

[apatriarca]

Dici il \( (\epsilon \cup a \cup b) \) ? \(\epsilon\) è la stringa vuota, per cui significa o la stringa vuota oppure una \(a\) o una \(b\). L'idea (facendo uso della relazione tra l'automa e l'espressione regolare) è che parti con una \(a\), poi vai avanti e indietro da \(q2\) a \(q3\) zero o più volte e infine finisci in \(q2\) oppure vai in \(q3\) e finisci la stringa lì.

[faby99s]

"apatriarca":Dici il \( (\epsilon \cup a \cup b) \) ? \(\epsilon\) è la stringa vuota, per cui significa o la stringa vuota oppure una \(a\) o una \(b\). L'idea (facendo uso della relazione tra l'automa e l'espressione regolare) è che parti con una \(a\), poi vai avanti e indietro da \(q2\) a \(q3\) zero o più volte e infine finisci in \(q2\) oppure vai in \(q3\) e finisci la stringa lì.

Ahhh okok capito....grazie mille sei stato molto gentile ☺️