[Espressioni Regolari]
Salve a tutti 
Sto studiando a livello teorico le espressioni regolari, quando mi sono imbattuto in uno esercizi che non riesco a risolvere probabilmente perché devo aver capito male qualcosa.
Esercizio 1
Dato il seguente linguaggio $ {w\in{0,1}$*$| k:w=k1} $ dire qual è l'espressione regolare riconosciuta dal linguaggio.
1) (00+01+10+11)*1
2) (0*1)*
3) (0*11*)(0*11*)*
4) 1*0*1
Se non sbaglio il linguaggio dice che accetta qualsiasi parola, l' importante è che finisca con 1. Dalle seguenti risposte penso che la giusta sia la 2) per il fatto che posso fare tutte le combinazioni possibili e alla fine dovrò sempre mettere un 1, il mio dubbio sorge qua, non avendo vincoli su k comporta anche che k stesso potrebbe essere vuoto , quindi la parola con solo 1 dovrebbe essere accettata dal linguaggio, ma con l'espressione regolare indicata (0*1)* non posso scegliere solo 1 ma dovrei fare la sequenza 0(quante volte voglio)e poi 1. Sto sbagliando qualcosa nel ragionamento oppure sto facendo confusione tra operatori di concatenazione e stella di kleene? Stesso discorso nella domanda numero 1, posso fare solo 1(quello a destra)? o devo per forza entrare prima nel blocco con la stella di kleene?
Grazie in anticipo a chi potrà darmi una mano.
Sto studiando a livello teorico le espressioni regolari, quando mi sono imbattuto in uno esercizi che non riesco a risolvere probabilmente perché devo aver capito male qualcosa.
Esercizio 1
Dato il seguente linguaggio $ {w\in{0,1}$*$| k:w=k1} $ dire qual è l'espressione regolare riconosciuta dal linguaggio.
1) (00+01+10+11)*1
2) (0*1)*
3) (0*11*)(0*11*)*
4) 1*0*1
Se non sbaglio il linguaggio dice che accetta qualsiasi parola, l' importante è che finisca con 1. Dalle seguenti risposte penso che la giusta sia la 2) per il fatto che posso fare tutte le combinazioni possibili e alla fine dovrò sempre mettere un 1, il mio dubbio sorge qua, non avendo vincoli su k comporta anche che k stesso potrebbe essere vuoto , quindi la parola con solo 1 dovrebbe essere accettata dal linguaggio, ma con l'espressione regolare indicata (0*1)* non posso scegliere solo 1 ma dovrei fare la sequenza 0(quante volte voglio)e poi 1. Sto sbagliando qualcosa nel ragionamento oppure sto facendo confusione tra operatori di concatenazione e stella di kleene? Stesso discorso nella domanda numero 1, posso fare solo 1(quello a destra)? o devo per forza entrare prima nel blocco con la stella di kleene?
Grazie in anticipo a chi potrà darmi una mano.
Risposte
La risposta 2 significa che la tua stringa è formata da zero o più sottostringhe formate da un numero arbitrario di zeri (anche nessuno) seguiti da un 1. La prima risposta ammette invece qualsiasi stringa di lunghezza dispari che termina con un uno.
Quindi mi pare di capire che la prima non può essere giusta, perché non posso comporre per esempio la stringa 01 che effettivamente è accettata dal linguaggio, mentre la seconda dovrebbe essere quella esatta?
Sì.
Ti ringrazio per l'aiuto.
Scusa se riapro la discussione però mi sono accorto che anche la risposta 3 soddisfa il linguaggio, eppure la domanda dice che solo una è giusta.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo