[Linguaggi Formali e Automi]
Salve a tutti,
sono nuovo nel forum ma ho navigato spesso in questo sito in cerca di soluzioni per i vari problemi di matematica e statistica. Ora devo studiare per l'esame di Linguaggi Formali e ho dei dubbi su alcuni esercizi.
Sia Σ={4,5}
Costruite un automa che accetti il linguaggio costituito da tutte le
stringhe sull'alfabeto Σ che, interpretate come numero in notazione decimale, rappresentano un
intero che diviso per 3 ha come resto 1.
L'automa dovrebbe contenere 3 stati che rappresentano i possibili resti della divisione per 3: 0, 1, 2.
Lo stato iniziale dovrebbe essere 0 in quanto all'inizio ho un resto di 0.
Lo stato finale dovrebbe essere 1 in quanto si accettano solo i numeri con resto 1.
Dopo queste considerazioni non so come continuare per determinare la funzione di transizione.
Qualcuno che ha un'idea?
sono nuovo nel forum ma ho navigato spesso in questo sito in cerca di soluzioni per i vari problemi di matematica e statistica. Ora devo studiare per l'esame di Linguaggi Formali e ho dei dubbi su alcuni esercizi.
Sia Σ={4,5}
Costruite un automa che accetti il linguaggio costituito da tutte le
stringhe sull'alfabeto Σ che, interpretate come numero in notazione decimale, rappresentano un
intero che diviso per 3 ha come resto 1.
L'automa dovrebbe contenere 3 stati che rappresentano i possibili resti della divisione per 3: 0, 1, 2.
Lo stato iniziale dovrebbe essere 0 in quanto all'inizio ho un resto di 0.
Lo stato finale dovrebbe essere 1 in quanto si accettano solo i numeri con resto 1.
Dopo queste considerazioni non so come continuare per determinare la funzione di transizione.
Qualcuno che ha un'idea?
Risposte
Ah, ok, pensavo fosse dovuto anche al fatto che non riuscivo io a vedere ciò che era presente al link per via del browser dello smartphone.
Riguardo alla tua soluzione c'è ancora qualcosa da sistemare.
Innanzitutto la freccia con $b$ da $q_0 non ci va$ in quanto l'automa non deve accettare stringhe che iniziano con tale simbolo. Poi, $q_5$ non ti serve, puoi andare direttamente da $q_4$ a $q_1$ con $a, b$. Infine da $q_1$ è sufficiente far partire una freccia che con $a$ va a finire in $q_6$ (che può essere così rinominato in $q_5$), che è di accettazione e da cui non parte nessuna freccia.
Con questa configurazione si può disquisire sul fatto che l'automa possa accettare o meno anche la stringa $aa$. In effetti anche zero lo si può vedere come multiplo di qualsiasi numero, ottenuto moltiplicando appunto lo stesso per zero.
Riguardo alla tua soluzione c'è ancora qualcosa da sistemare.
Innanzitutto la freccia con $b$ da $q_0 non ci va$ in quanto l'automa non deve accettare stringhe che iniziano con tale simbolo. Poi, $q_5$ non ti serve, puoi andare direttamente da $q_4$ a $q_1$ con $a, b$. Infine da $q_1$ è sufficiente far partire una freccia che con $a$ va a finire in $q_6$ (che può essere così rinominato in $q_5$), che è di accettazione e da cui non parte nessuna freccia.
Con questa configurazione si può disquisire sul fatto che l'automa possa accettare o meno anche la stringa $aa$. In effetti anche zero lo si può vedere come multiplo di qualsiasi numero, ottenuto moltiplicando appunto lo stesso per zero.
Grazie onlyRefree!
Volevo chiederti qualcosa di diverso, date le seguenti espressioni regolari devo disegnare i relativi automi:
1) ( (0 + 1)(0 + 1) )* + ( (0 + 1)(0 + 1)(0 + 1) )*
2) ( (0 + 1 + epsilon)(0 + 1)(0 + 1) )*
E' possibile semplificare le espressioni ottenendo queste?
1) ( 0+1 )*
2) ( 0 + 1 + epsilon )*
Volevo chiederti qualcosa di diverso, date le seguenti espressioni regolari devo disegnare i relativi automi:
1) ( (0 + 1)(0 + 1) )* + ( (0 + 1)(0 + 1)(0 + 1) )*
2) ( (0 + 1 + epsilon)(0 + 1)(0 + 1) )*
E' possibile semplificare le espressioni ottenendo queste?
1) ( 0+1 )*
2) ( 0 + 1 + epsilon )*
1) No perché ad esempio la stringa $1$ appartiene al linguaggio nella sua versione originale ma non a quella che hai riscritto;
2) No. Lo si verifica prendendo lo stesso esempio proposto al punto precedente (con la differenza che qui la stringa $1$ appartiene all'espressione che hai riscritto e non alla prima).
Ricorda che per passare da un'espressione regolare ad una sua forma semplificata bisogna sempre effettuare i dovuti passaggi.
2) No. Lo si verifica prendendo lo stesso esempio proposto al punto precedente (con la differenza che qui la stringa $1$ appartiene all'espressione che hai riscritto e non alla prima).
Ricorda che per passare da un'espressione regolare ad una sua forma semplificata bisogna sempre effettuare i dovuti passaggi.
Ho riguardato le proprietà delle espressioni regolari sul libro: commutativa per l'unione,associativa per l'unione,associativa per la concatenazione, distributiva per la concatenazione, idempotenza, chiusura.
Non capisco da dove cominciare per semplificare..
Non capisco da dove cominciare per semplificare..
Se due espressioni regolari generano linguaggi diversi è sufficiente trovare un controesempio con una stringa appartenente al primo ma non al secondo linguaggio.
Se può esserti utile puoi trovare qui una spiegazione semplice ed interessante su come semplificare le espressioni regolari.
Se può esserti utile puoi trovare qui una spiegazione semplice ed interessante su come semplificare le espressioni regolari.
Nuovo esercizio onlyRefree 
e grazie per il link
Sia L il linguaggio riconosciuto dal seguente automa:
Disegnate un automa per L^c. Determinate un'espressione regolare per LL^c.
Per quanto riguarda L^c ho letto che per ottenere il complemento di un automa e' sufficiente invertire gli stati accettanti con quelli non accettanti. Per quanto riguarda la determinazione dell'espressione regolare tra L e il suo complemento non capisco come fare.
L'espressione regolare di L dovrebbe essere: L=(ab*(a+b))*ab*
Come si determina l'espressione regolare di L complemento? Come si ottiene poi la concatenazione con L?
Grazie
e grazie per il linkSia L il linguaggio riconosciuto dal seguente automa:
| a | b | |
|---|---|---|
| q_2 | / | * q_2 |
Disegnate un automa per L^c. Determinate un'espressione regolare per LL^c.
Per quanto riguarda L^c ho letto che per ottenere il complemento di un automa e' sufficiente invertire gli stati accettanti con quelli non accettanti. Per quanto riguarda la determinazione dell'espressione regolare tra L e il suo complemento non capisco come fare.
L'espressione regolare di L dovrebbe essere: L=(ab*(a+b))*ab*
Come si determina l'espressione regolare di L complemento? Come si ottiene poi la concatenazione con L?
Grazie
Ciao 
L'espressione che hai proposto per $L$ è corretta. L'espressione del suo complemento va fatta partendo dall'automa che riconosce tale linguaggio (che da come ho capito sai correttamente costruire).
Con "concatenazione con $L$" intendi l'operazione di concatenazione tra i linguaggi $L$ ed $L^C$
Se sì in tal caso bisogna idealmente stabilire come sono fatte le stringhe che sono il risultato dell'unione tra quelle di $L$ e quelle di $L^C$. Una volta fatto ciò si può scrivere un'espressione regolare anche per queste.
L'espressione che hai proposto per $L$ è corretta. L'espressione del suo complemento va fatta partendo dall'automa che riconosce tale linguaggio (che da come ho capito sai correttamente costruire).
Con "concatenazione con $L$" intendi l'operazione di concatenazione tra i linguaggi $L$ ed $L^C$
Se sì in tal caso bisogna idealmente stabilire come sono fatte le stringhe che sono il risultato dell'unione tra quelle di $L$ e quelle di $L^C$. Una volta fatto ciò si può scrivere un'espressione regolare anche per queste.
Salve ragazzi,
riapro il thread in quanto ho alcuni esercizi simili a quelli proposti da 4mac07.
1) Costruire un automa che accetti il linguaggio costituito da tutte le
stringhe sull'alfabeto {a,b} in cui a e b si alternano, iniziando da a e terminando con b.
2)Costruire un automa che accetti il linguaggio costituito da tutte le
stringhe sull'alfabeto {a,b} in cui ogni a e seguita immediatamente da una b.
Sembrano simili come esercizi, potete fare degli esempi di stringhe accettate e non accettate?
Grazie
riapro il thread in quanto ho alcuni esercizi simili a quelli proposti da 4mac07.
1) Costruire un automa che accetti il linguaggio costituito da tutte le
stringhe sull'alfabeto {a,b} in cui a e b si alternano, iniziando da a e terminando con b.
2)Costruire un automa che accetti il linguaggio costituito da tutte le
stringhe sull'alfabeto {a,b} in cui ogni a e seguita immediatamente da una b.
Sembrano simili come esercizi, potete fare degli esempi di stringhe accettate e non accettate?
Grazie
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo