Diagrammi stato-transizioni
Ciao a tutti, stavo cercando di svolgere questo esercizio:
Disegnare il diagramma stato-transizione di automi finiti deterministici che riconoscano i linguaggi sull’alfabeto {a, b} che soddisfano una delle seguenti condizioni:
1. ${a^n b^n | 0 <= n <= 3}$
2. ogni occorrenza del carattere a sia seguita immediatamente da almeno due occorrenze del carattere b.
3. ogni occorrenza del carattere a sia seguita immediatamente da esattamente due occorrenze del carattere b.
4. contengano almeno un’occorrenza della sottostriga aa.
5. inizino con almeno due a e terminino con almeno due b.
6. contengano un numero pari di a e un numero pari di b.
Che cos'è un "diagramma stato-transizione"? E' semplicemente un automa?
La numero (1) che automa genera? Io scriverei la grammatica in questo modo:
$S -> \epsilon | A | aAb | aaAbb$
$A -> ab$
E' corretto? Però come faccio a fare l'automa a partire da questa grammatica dato che non è unilineare destra?
Per le altre (2, 3, 4, 5 e 6) so l'espressione regolare, quindi ora dovrei generare la grammatica a partire dall'espressione regolare e poi creo l'automa. E' un procedimento che potrebbe andare?
Esempio:
2. ogni occorrenza del carattere a sia seguita immediatamente da almeno due occorrenze del carattere b.
Espressione regolare: b*(abb+)*
Grammatica:
$S -> \epsilon | bB | A$
$A -> abbB$
$B -> bB | b$
e poi costruisco l'automa..
Grazie
Disegnare il diagramma stato-transizione di automi finiti deterministici che riconoscano i linguaggi sull’alfabeto {a, b} che soddisfano una delle seguenti condizioni:
1. ${a^n b^n | 0 <= n <= 3}$
2. ogni occorrenza del carattere a sia seguita immediatamente da almeno due occorrenze del carattere b.
3. ogni occorrenza del carattere a sia seguita immediatamente da esattamente due occorrenze del carattere b.
4. contengano almeno un’occorrenza della sottostriga aa.
5. inizino con almeno due a e terminino con almeno due b.
6. contengano un numero pari di a e un numero pari di b.
Che cos'è un "diagramma stato-transizione"? E' semplicemente un automa?
La numero (1) che automa genera? Io scriverei la grammatica in questo modo:
$S -> \epsilon | A | aAb | aaAbb$
$A -> ab$
E' corretto? Però come faccio a fare l'automa a partire da questa grammatica dato che non è unilineare destra?
Per le altre (2, 3, 4, 5 e 6) so l'espressione regolare, quindi ora dovrei generare la grammatica a partire dall'espressione regolare e poi creo l'automa. E' un procedimento che potrebbe andare?
Esempio:
2. ogni occorrenza del carattere a sia seguita immediatamente da almeno due occorrenze del carattere b.
Espressione regolare: b*(abb+)*
Grammatica:
$S -> \epsilon | bB | A$
$A -> abbB$
$B -> bB | b$
e poi costruisco l'automa..
Grazie
Risposte
Ciao stefano86 
Sì, esatto, un normale automa a stati finiti.
La tua grammatica è corretta solo che...non capisco come mai per la prima regola $S -> \epsilon | A | aAb | aaA b b$ il LaTeX non ti stampi il $b b$ finale (taglia le ultime due lettere). In ogni caso puoi semplicemente utilizzare il simbolo iniziale ed elencare direttamente tutte le produzioni senza ricorrere ad $A$. Ecco come:
\[
S -> \epsilon | ab | aabb | aaabbb
\]
Più che l'espressione regolare ti viene descritto il linguaggio che deve risultare. In ogni caso con un attimo di occhio puoi creare anche direttamente l'automa senza tanti problemi, dipende da come ti trovi meglio. L'importante è procedere sempre passo passo riconoscendo di volta in volta le varie parti delle stringhe accettate dal linguaggio.
L'espressione regolare proposta non va bene perché potresti avere una sequenza di più di due $b$ dopo ogni $a$. Difatti la tua espressione ti impedisce di riconoscere ad esempio la stringa $a b b b b b b b b b b b b b b b$. Altro suggerimento: la notazione (a b b+) * si può scrivere in maniera più semplice come $(a b b)^+$. Un'espressione regolare corretta potrebbe essere ad esempio (b + (abbb*))*. Perdona se in queste ultime espressioni non ho sempre usato il LaTeX ma anche lo star (*) talvolta non lo stampa.
"stefano86":
[...]
Che cos'è un "diagramma stato-transizione"? E' semplicemente un automa?
[...]
Sì, esatto, un normale automa a stati finiti.
"stefano86":
[...]
La numero (1) che automa genera? Io scriverei la grammatica in questo modo:
$S -> \epsilon | A | aAb | aaAbb$
$A -> ab$
E' corretto? Però come faccio a fare l'automa a partire da questa grammatica dato che non è unilineare destra?
[...]
La tua grammatica è corretta solo che...non capisco come mai per la prima regola $S -> \epsilon | A | aAb | aaA b b$ il LaTeX non ti stampi il $b b$ finale (taglia le ultime due lettere). In ogni caso puoi semplicemente utilizzare il simbolo iniziale ed elencare direttamente tutte le produzioni senza ricorrere ad $A$. Ecco come:
\[
S -> \epsilon | ab | aabb | aaabbb
\]
"stefano86":
[...]
Per le altre (2, 3, 4, 5 e 6) so l'espressione regolare, quindi ora dovrei generare la grammatica a partire dall'espressione regolare e poi creo l'automa. E' un procedimento che potrebbe andare?
[...]
Più che l'espressione regolare ti viene descritto il linguaggio che deve risultare. In ogni caso con un attimo di occhio puoi creare anche direttamente l'automa senza tanti problemi, dipende da come ti trovi meglio. L'importante è procedere sempre passo passo riconoscendo di volta in volta le varie parti delle stringhe accettate dal linguaggio.
"stefano86":
[...]
Esempio:
2. ogni occorrenza del carattere a sia seguita immediatamente da almeno due occorrenze del carattere b.
Espressione regolare: b*(abb+)*
Grammatica:
$S -> \epsilon | bB | A$
$A -> abbB$
$B -> bB | b$
e poi costruisco l'automa..
Grazie
L'espressione regolare proposta non va bene perché potresti avere una sequenza di più di due $b$ dopo ogni $a$. Difatti la tua espressione ti impedisce di riconoscere ad esempio la stringa $a b b b b b b b b b b b b b b b$. Altro suggerimento: la notazione (a b b+) * si può scrivere in maniera più semplice come $(a b b)^+$. Un'espressione regolare corretta potrebbe essere ad esempio (b + (abbb*))*. Perdona se in queste ultime espressioni non ho sempre usato il LaTeX ma anche lo star (*) talvolta non lo stampa.
Grazie, effettivamente la tua grammatica è più semplice.
Secondo me l'espressione regolare $(a b b^+)$* è corretta e accetta $a b b b b b b b b b b b b b b b $. Perchè dici di no?
Secondo me l'espressione regolare $(a b b^+)$* è corretta e accetta $a b b b b b b b b b b b b b b b $. Perchè dici di no?
Perché $( a a b^+)$*$=( a a b)^+ = \{aab, aabaab, aabaabaab, ...\}$ e come vedi $a b b b b b b b b b b b b b b b$ non appartiene alle stringhe generate mediante questa espressione regolare. Basta che rifletti sul significato degli operatori chiusura di Kleen e Kleen plus.
mm no. $(a b b^+)$* $=(a b (b)^+)$* $= {\epsilon, a a b, a a b b, a a b b b, a a b a a b b b b b b b, a a b a a b b b b b a a b, ...}$.
L'operazione "croce" è applicata solo alla $b$ e non a $a b b $..
L'operazione "croce" è applicata solo alla $b$ e non a $a b b $..
Sí, in effetti lí sul momento la notazione mi ha tratto in errore...
Resta però il fatto che l'espressione regolare proposta non é corretta.
Resta però il fatto che l'espressione regolare proposta non é corretta.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo