.dsy:it. (http://www.dsy.it/forum/)
- Linguaggi formali e automi (http://www.dsy.it/forum/forumdisplay.php?forumid=132)
-- Pighizzini-Pdf Esercizi (http://www.dsy.it/forum/showthread.php?threadid=43979)

Pighizzini-Pdf Esercizi

Ciao a tutti,
io sto studiando LFA sul libro di Pighizzini e volevo chiedere se c'e' qualcuno che e' interessato a fare i 61 esercizi che il prof ha postato sul suo sito.
Piu' siamo e meglio e'. Una volta finiti gli esercizi possiamo postare le soluzioni sul forum in modo da aiutare gli altri.

Esercizio 1
Sia  = Σ={a,b}
Costruite un automa che accetti il linguaggio costituito da tutte le
stringhe sull'alfabeto  che contengono almeno una a seguita da una b.
Esprimete questo linguaggio con un'espressione regolare.

http://imageshack.com/a/img540/8918/bdGOxP.jpg
Io ho fatto cosi, e' giusto?

Direi di si, ma al posto di (epsilon + b)^* metterei b^* che è equivalente!

Originally posted by Cronovirus
Direi di si, ma al posto di (epsilon + b)^* metterei b^* che è equivalente!

Originally posted by luca2708
Grazie Cronovirus! Man mano che li faccio, li aggiungo in un PDF da condividere.

Esercizio 2
Sia Σ={a,b}
Costruite un automa che accetti il linguaggio costituito da tutte le
stringhe sull'alfabeto Σ in cui a e b si alternano, iniziando da a e terminando con b.
Esprimete questo linguaggio con un'espressione regolare.

http://imageshack.com/a/img540/9897/L28llm.jpg

Esercizio 3
Sia Σ={a,b}
Costruite un automa che accetti il linguaggio costituito da tutte le
stringhe sull'alfabeto Σ in cui ogni a e seguita immediatamente da una b.
Esprimete questo linguaggio con un'espressione regolare.

http://imageshack.com/a/img661/9646/RcuuUm.jpg

Esercizio 4
Sia Σ={0,1}
Costruite un automa che accetti il linguaggio costituito da tutte le
stringhe sull'alfabeto  Σ che, interpretate come numeri in notazione binaria, rappresentano multipli di 4.
Esprimete questo linguaggio con un'espressione regolare.

Su questo non sono sicuro, io ho interpretato i multipli di 4 come quei numeri in binario che terminano con doppio zero.

http://imageshack.com/a/img537/4121/5kKmWM.jpg

Corretto

Originally posted by Cronovirus
Corretto

Sarebbe meglio se riuscissi a caricare direttamente sul forum le immagini con gli esercizi corretti così anche tra qualche anno saranno disponibili a tutti
Io posso aiutarti in questi primi esercizi per quello che mi ricordo, magari su quelli più complicati spero che intervenga qualcun altro!!
Ma per il momento continuiamo così

Ok, spero che si aggiungano altri

Esercizio 5
Sia Σ={a,b}
Costruite un automa che accetti il linguaggio costituito da tutte le
stringhe sull'alfabeto Σ in cui il secondo simbolo e' una a.
Esprimete questo linguaggio con un'espressione regolare.

E' possibile semplificare la seguente espressione regolare?
( (0+1)(0+1) )* + ( (0+1)(0+1)(0+1) )*

Postero' anche io qualche esercizio!
Nel 5 al posto di:

(aa+ba)(a+b)*

(a+b)a(a+b)*

Originally posted by luca2708
E' possibile semplificare la seguente espressione regolare?
( (0+1)(0+1) )* + ( (0+1)(0+1)(0+1) )*

Inizio a postare degli esercizi che ho fatto oggi:

• Esercizi 11,12,13 - link
  
• Esercizi 14,15,16,17 - link
  
• Esercizi 18,19,20,21,22 - link
  
• Esercizi 23,24 - link