(informatica teorica) espressioni regolari

[m3c4]

scusate oggi non trovo pace...!!

secondo e ultimo esercizio-aiutino che vi chiedo e poi basta, lo giuro!!

trovare l'espressione regolare per il linguaggio:
L = {w $in$ {0,1}* | w non contiene 101 come sottostringa}

ora, ne ho provati tanti, e quello che si avvicina di più alla soluzione è (100)* U (010)*
ho costruito anche un NFA (automa a stati finiti non deterministico) corrispondente, ma non mi convince.
intanto il primo dubbio è: se ho una sottostringa di 101, vuol dire che tutte le stringhe considerate devono avere cardinalità maggiore o uguale a 3, oppure vanno bene anche quelle di lunghezza minore di 3??
ma soprattutto, l'espressione regolare è quella giusta???

Mah!!

grazie mille a tutti anticipatamente!

[Rggb1]

Perché non provi a creare il DFA corrispondente? E' abbastanza semplice: avrà tutti stati finali tranne uno, e si arriva a questo unico stato non finale con le transazioni corrispondenti alla stringa '101'.

Partendo da stato $0$, se trovi '1' passi in stato $1$
Da stato $1$ se trovi '0' passi in stato $2$
Da stato $2$ se trovi '1' passi in stato $3$, non finale.
Da stato $3$ per qualunque input rimani in stato $3$ (l'automa ha già riconosciuto '101')
Completi con le transazioni mancanti e converti il tutto in espressione regolare nel modo consueto.

E' il modo tipico per costruire DFA che riconoscano stringhe non contenenti un dato pattern.

[m3c4]

ok fatto!
quindi una espressione regolare equivalente può essere :
dato $\Sigma$={0,1}
$\Sigma$* $\Sigma$* 0*

è corretta??

[Rggb1]

Non direi... dovresti avere qualcosa tipo $(0^star 1 1^star 0 0)^star$

Che automa ti risulta? Forse hai sbagliato qualche transizione.

EDIT: fra l'altro mi accorgo che la mia RE è incompleta, ma tant'è... basta completarla.