Esercizi espressioni regolari
Innanzitutto buona giornata.
Inserisco di seguito alcuni esercizi che ho fatto in merito alla definizione di linguaggi regolari mediante espressioni regolari.
Ho a disposizione le operazioni di unione([tex]+[/tex]), concatenazione([tex]\cdot[/tex]) e chiusura di Kleene([tex]^*[/tex]).
1)[tex]\left\{w \in {\left\{0,1\right\}}^{*} \mid \textit{ogni coppia di 0 adiacenti compaia prima di ogni coppia di 1 adiacenti} \right\}[/tex]
[tex](1+0+(010+10)^*)(0+00^*1)^*(1+(11^*0))^*[/tex]
2)[tex]\left\{w \in {\left\{0,1\right\}}^{*} \mid \textit{il numero di 0 e' divisibile per 5} \right\}[/tex]
[tex](1+01^*01^*01^*01^*0)^*[/tex]
3)[tex]\left\{w \in {\left\{0,1\right\}}^{*} \mid \textit{non contiene la sottostringa 101} \right\}[/tex]
[tex]0^*(1+0^*1^*000^*)^*0^*[/tex]
4)[tex]\left\{w \in {\left\{0,1\right\}}^{*} \mid \textit{in ogni prefisso di w la differenza tra il numero di 0 e quello di 1 sia minore di 2} \right\}[/tex]
[tex](((00+ \epsilon)(11))^*((01)((01)^*0)^*+(10)((10)^*0)^*)^*+0+1+\epsilon)[/tex]
5)[tex]\left\{w \in {\left\{0,1\right\}}^{*} \mid \textit{non contiene la sottostringa 000} \right\}[/tex]
[tex]1^*(011^*+0011^*)^*(0+00+\epsilon)[/tex]
Vi ringrazio dell'attenzione e vi chiedo, se possibile, di verificarne la correttezza.
Ancora buona giornata.
Inserisco di seguito alcuni esercizi che ho fatto in merito alla definizione di linguaggi regolari mediante espressioni regolari.
Ho a disposizione le operazioni di unione([tex]+[/tex]), concatenazione([tex]\cdot[/tex]) e chiusura di Kleene([tex]^*[/tex]).
1)[tex]\left\{w \in {\left\{0,1\right\}}^{*} \mid \textit{ogni coppia di 0 adiacenti compaia prima di ogni coppia di 1 adiacenti} \right\}[/tex]
[tex](1+0+(010+10)^*)(0+00^*1)^*(1+(11^*0))^*[/tex]
2)[tex]\left\{w \in {\left\{0,1\right\}}^{*} \mid \textit{il numero di 0 e' divisibile per 5} \right\}[/tex]
[tex](1+01^*01^*01^*01^*0)^*[/tex]
3)[tex]\left\{w \in {\left\{0,1\right\}}^{*} \mid \textit{non contiene la sottostringa 101} \right\}[/tex]
[tex]0^*(1+0^*1^*000^*)^*0^*[/tex]
4)[tex]\left\{w \in {\left\{0,1\right\}}^{*} \mid \textit{in ogni prefisso di w la differenza tra il numero di 0 e quello di 1 sia minore di 2} \right\}[/tex]
[tex](((00+ \epsilon)(11))^*((01)((01)^*0)^*+(10)((10)^*0)^*)^*+0+1+\epsilon)[/tex]
5)[tex]\left\{w \in {\left\{0,1\right\}}^{*} \mid \textit{non contiene la sottostringa 000} \right\}[/tex]
[tex]1^*(011^*+0011^*)^*(0+00+\epsilon)[/tex]
Vi ringrazio dell'attenzione e vi chiedo, se possibile, di verificarne la correttezza.
Ancora buona giornata.
Risposte
L'ho guardata velocemente, ma la prima mi sembra sbagliata. Mi sembra per esempio che 11 sia una parola valida (concateni 1, la stringa vuota e un altro 1). La seconda mi sembra corretta. La terza sbagliata. Puoi infatti avere una sequenza di 0, poi scegliere 1 e poi scegliere uno zero, un uno e un numero qualsiasi di zero. Sulla quarta ci devo pensare un po' di più, mentre la quinta mi sembra corretta.
Ti ringrazio delle correzioni, in effetti ho però ancora qualche dubbio:
- nel primo esercizio le stringe appartengono al linguaggio se "ogni coppia di 0 adiacenti compare prima di ogni coppia di 1 adiacenti" non è consentita la stringa [tex]11[/tex] come da te peraltro specificata quale invalidante la regex in questione? Io l'ho ipotizzata appartenente al linguaggio in questione, tralaltro diverso da un possibile linguaggio che prevede che "ogni coppia di 1 adiacenti è preceduta da una coppia di 0"... della serie se gli zeri sono presenti allora le coppie di zeri devono precedere quelli di uni, altrimenti posso anche inserire stringhe formate da soli uni a piacimento.
- per la terza regex invece cosa ne dici di questa: [tex]1^*+(0^*+1^*0)(00^*1^*00^*)^*(01^*)[/tex]??
Ti ringrazio ancora.
- nel primo esercizio le stringe appartengono al linguaggio se "ogni coppia di 0 adiacenti compare prima di ogni coppia di 1 adiacenti" non è consentita la stringa [tex]11[/tex] come da te peraltro specificata quale invalidante la regex in questione? Io l'ho ipotizzata appartenente al linguaggio in questione, tralaltro diverso da un possibile linguaggio che prevede che "ogni coppia di 1 adiacenti è preceduta da una coppia di 0"... della serie se gli zeri sono presenti allora le coppie di zeri devono precedere quelli di uni, altrimenti posso anche inserire stringhe formate da soli uni a piacimento.
- per la terza regex invece cosa ne dici di questa: [tex]1^*+(0^*+1^*0)(00^*1^*00^*)^*(01^*)[/tex]??
Ti ringrazio ancora.
Sulla prima, in effetti l'interpretazione del testo potrebbe anche essere uguale alla tua. Ci darò un occhiata. La tre potrebbe essere valida.
Continuo con alcuni esercizi sulle regex e gli automi a stati finiti ad esse associate.
1)[tex]L=\left\{w \in {\left\{1,2,3\right\}}^* \mid
\textit{w inizia con 3, finisce con 2 e contiene un'unica sottostringa di soli 1 di lunghezza pari maggiore o uguale a 2}\right\}[/tex]
[tex]3(3+2)^*11(11)^*(3+2)^*2[/tex]
2)[tex]\left\{w \in {\left\{1,2\right\}}^* \mid \textit{ogni 1 e' seguito sempre da uno o piu' 2 a meno che 1 sia l'ultimo carattere} \right\}[/tex]
[tex](122^*+2)^*(1+\epsilon)[/tex]
3)Trovare l'automa a stati finiti associato a tale linguaggio e da questo ricavare la regex associata:
[tex]\left\{w \in {\left\{0,1\right\}}^* \mid \textit{w contenga almeno tre simboli ed il primo carattere sia uguale al penultimo} \right\}[/tex]
Automa trovato:
Da questo mediante il metodo per eliminazione di stati trovo la regex associata
[tex]0(0+1)^*0(0+1)+1(0+1)^*1(0+1)[/tex]
4)Trovare l'automa a stati finiti associato a tale linguaggio e da questo ricavare la regex associata:
[tex]\left\{w \in {\left\{0,1\right\}}^* \mid \textit{l'ultimo carattere di w non compare mai prima} \right\}[/tex]
Automa trovato:
Da questo mediante il metodo per eliminazione di stati trovo la regex associata
[tex](0+1)+(0(1+00^*1)+1(0+11^*0))[/tex]
1)[tex]L=\left\{w \in {\left\{1,2,3\right\}}^* \mid
\textit{w inizia con 3, finisce con 2 e contiene un'unica sottostringa di soli 1 di lunghezza pari maggiore o uguale a 2}\right\}[/tex]
[tex]3(3+2)^*11(11)^*(3+2)^*2[/tex]
2)[tex]\left\{w \in {\left\{1,2\right\}}^* \mid \textit{ogni 1 e' seguito sempre da uno o piu' 2 a meno che 1 sia l'ultimo carattere} \right\}[/tex]
[tex](122^*+2)^*(1+\epsilon)[/tex]
3)Trovare l'automa a stati finiti associato a tale linguaggio e da questo ricavare la regex associata:
[tex]\left\{w \in {\left\{0,1\right\}}^* \mid \textit{w contenga almeno tre simboli ed il primo carattere sia uguale al penultimo} \right\}[/tex]
Automa trovato:
Da questo mediante il metodo per eliminazione di stati trovo la regex associata
[tex]0(0+1)^*0(0+1)+1(0+1)^*1(0+1)[/tex]
4)Trovare l'automa a stati finiti associato a tale linguaggio e da questo ricavare la regex associata:
[tex]\left\{w \in {\left\{0,1\right\}}^* \mid \textit{l'ultimo carattere di w non compare mai prima} \right\}[/tex]
Automa trovato:
Da questo mediante il metodo per eliminazione di stati trovo la regex associata
[tex](0+1)+(0(1+00^*1)+1(0+11^*0))[/tex]
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo