[ETC] Espressione regolare

[Djstez]

ETC elementi teoria della computazione

Ho un problema con quest'e esercizio

Dato L = {w appartenente {a,b}* dove w ha il carattere b solo nelle posizioni pari } ad esempio abaa abab etc...
Devo definire un ESPRESSIONE REGOLARE che descriva L

[anonymous_be1147]

Ciao, non so nulla di teoria della computazione, però se dovessi scrivere un'espressione regolare per trovare quelle parole scriverei questa

/\b(a(a|b))+\b/g

verifica: http://refiddle.com/gme (in verde le parole che corrispondono)

Forse nel tuo caso, se non serve distinguere le parole e delimitare la RE, si scriverebbe semplicemente

(a(a|b))+

.

[Djstez]

Grazie per la risposta pero questa è l espressione regolare. definirla credo che dovrebbe essere fatta con la ricorsione che non ho idea come risolvere.

[anonymous_be1147]

Secondo me la RE scritta descrive tutte e sole le stringhe che hanno il carattere b nelle posizioni pari e cioè l'insieme L, però vediamo se qualcuno che ha studiato queste cose ci può dire qualcosa in più. Sicuramente non è la notazione formale che si usa in questi casi, e forse andrebbe riscritta così: \( \left(a\left(a + b\right)\right)^{*} \), se ho capito qualcosa di questa dispensa...
Di più non so, mi spiace di non essere stato d'aiuto.

[apatriarca]

L'insieme che si sta analizzando non è formato dalle sole parole di lunghezza pari. Per cui le soluzioni finora proposte non sono corrette. Usando la sintassi comunemente adottata nei software (e non nella teoria) sarebbe qualcosa come \((a(a|b))^*a?\). Usando una notazione più vicina a quella della teoria direi che la seguente dovrebbe essere corretta \((a \cdot (a + b))^*\cdot ( \epsilon + a )\).

[anonymous_be1147]

In effetti ho dimenticato il caso delle stringhe terminanti con lettere a. Grazie della correzione.