[Linguaggi Formali e Automi]

[4mac07]

Nuovo esercizio:)
Sia Σ={a,b}. Costruite un automa nondeterministico che accetti il linguaggio costituito da tutte le stringhe sull'alfabeto Σ nelle quali il terzultimo e il penultimo simbolo sono uguali.
Esprimete questo linguaggio con un'espressione regolare.

L'espressione regolare a cui avevo pensato e' la seguente: (a+b)*(aa+bb)(a+b)
Riguardo all'NFA ho pensato a questa tabella delle transizioni che non e' ancora completa:

δ	a	b
->q_0	{q_0,q_1}	{q_0,q_2}
q_1	q_3	q_2
q_2	q_1	q_4
*q_3	q_3	/
*q_4	/	q_4

Il dubbio rimane sugli stati q_3 e q_4 in quanto non so come gestire il caso in cui arrivi l'ultimo simbolo in modo da accettare anche le stringhe che terminano con: '...aab' e '...bba'

[onlyReferee]

Ciao
Da $q_1$ non hai la necessità di andare a $q_2$ e viceversa (la parte precedente al terzultimo simbolo della stringa la puoi generare tutta con $q_0$). Da $q_2$ puoi andare direttamente in $q_3$ con $b$ (basta un solo stato che ci indica di aver ricevuto in input tutti i simboli della nostra stringa fino al penultimo). Per quanto detto nella frase precedente $q_3$ non può essere di accettazione. Infine da $q_3$ vai in $q_4$, stato finale, sia con $a$ che con $b$ (l'ultimo simbolo non ha vincoli).

[4mac07]

Grazie mille onlyRefree! Il tuo parere mi e' molto utile per capire meglio

[4mac07]

onlyRefree come interpreti questa consegna?

Sia Σ={a,b}. Costruite un automa che accetti l'insieme delle stringhe contenenti due a separate da un numero di simboli multiplo di 4.
Esprimete questo linguaggio con un'espressione regolare.

E' giusto secondo te pensare che le due 'a' siano separate da un numero multiplo di 4 simboli 'b'.
'aaaaaaaabbbba' viene accettata
'babbabaaaaaaa' non accettata
In pratica le 'b' devono essere multiplo di 4, giusto?

[onlyReferee]

Ciao
No, i simboli tra le due $a$ (quella iniziale e quella finale) possono essere qualsiasi (sia $a$ che $b$) purché in quantità pari ad un multiplo di quattro. Pertanto l'automa dovrà riconoscere ad esempio le stringhe $a b b b b b b b ba$, $aaaaaa$, $a b a b b a b a a b b b b a$ e $a b b b b a a a a a$ ma non $aba$, $aaa$ e $a a b b a b a b a$.
Immagino ti sia richiesto di costruire un automa non deterministico.

[4mac07]

Non e' specificato ma probabilmente e' non deterministico, lo devo rifare in quanto ho interpretato male.
L'espressione regolare diventa (a+b)*a(aaaa+bbbb)*a(a+b)*?

[onlyReferee]

No, questa espressione non è corretta. Innanzitutto hai una $a$ all'inizio ed una alla fine della stringa. Poi per creare la parte centrale della stringa devi avere una "base" composta da quattro espressioni consecutive in cui si può scegliere tra $a$ e $b$. Per avere multipli di quattro di questa base è sufficiente iterare la stessa.

[4mac07]

Non sono sicuro di aver capito...la parte centrale di prima non va bene? a(aaaa+bbbb)*a
riconosce stringhe del tipo '...a aaaa a...' , '...a bbbb a...'

[4mac07]

onlyRefree in base alle tue dritte ho prodotto questa soluzione, forse si puo' semplificare ma intanto funziona sugli input che hai suggerito.
Inoltre mi sorge un dubbio, sul testo del problema dice "stringhe contenenti due a separate da un numero di simboli multiplo di 4", può anche accettare che tra due 'a' i siano 'abab' / 'baba' / 'abba' / 'aabb' ecc oppure devono per forza essere 4 simboli uguali come detto precedentemente?

http://i60.tinypic.com/9qitn5.png

[onlyReferee]

Ciao
Perdona il ritardo nella risposta, sono stato via nel weekend. Comunque è corretto quanto hai descritto nel tuo ultimo post: quel gruppo centrale di simboli può essere composto sia da $a$ che da $b$.
Non so perché cliccando sull'url da te postato non vedo l'immagine...