Esercizio sulle stringhe/alfabeti
Ciao a tutti, ho questo esercizio da svolgere ma non saprei da dove iniziare:
Si dia un'espressione regolare sull'alfabeto {a, b, c} che rappresenti il linguaggio le cui parole sono formate da prefissi di un numero qualsivoglia di a, seguiti da un numero qualsivoglia di b e terminanti con almeno una delle stringhe ca o cb.
Si dia un'espressione regolare sull'alfabeto {a, b, c} che rappresenti il linguaggio le cui parole sono formate da prefissi di un numero qualsivoglia di a, seguiti da un numero qualsivoglia di b e terminanti con almeno una delle stringhe ca o cb.
Risposte
Ciao 
Innanzitutto ti chiedo: c'è qualcosa in particolare che non ti è chiaro sulle espressioni regolari
Venendo all'esercizio, bisogna che cerchi ci costruire la stringa in base ai requisiti un passo per volta partendo da sinistra ed applicando appunto la sintassi delle espressioni regolari che ben conosci (operatori di Kleene star, Kleene plus, ecc).
Fermo restando che con "un numero qualsivoglia" di $a$" (oppure $b$ o anche $c$) si intende anche il caso limite di nessuna $a$, sicuramente la nostra espressione regolare inizierà con $a^{\star}$. Riesci a continuare
Innanzitutto ti chiedo: c'è qualcosa in particolare che non ti è chiaro sulle espressioni regolari
Venendo all'esercizio, bisogna che cerchi ci costruire la stringa in base ai requisiti un passo per volta partendo da sinistra ed applicando appunto la sintassi delle espressioni regolari che ben conosci (operatori di Kleene star, Kleene plus, ecc).
Fermo restando che con "un numero qualsivoglia" di $a$" (oppure $b$ o anche $c$) si intende anche il caso limite di nessuna $a$, sicuramente la nostra espressione regolare inizierà con $a^{\star}$. Riesci a continuare
"onlyReferee":
Ciao
Innanzitutto ti chiedo: c'è qualcosa in particolare che non ti è chiaro sulle espressioni regolari
Venendo all'esercizio, bisogna che cerchi ci costruire la stringa in base ai requisiti un passo per volta partendo da sinistra ed applicando appunto la sintassi delle espressioni regolari che ben conosci (operatori di Kleene star, Kleene plus, ecc).
Fermo restando che con "un numero qualsivoglia" di $a$" (oppure $b$ o anche $c$) si intende anche il caso limite di nessuna $a$, sicuramente la nostra espressione regolare inizierà con $a^{\star}$. Riesci a continuare
Ciao ti ringrazio per la risposta, avrei un dubbio, nel caso in cui $ a^nb^mc^l $ con $ n,m,l != 0 $ come posso svolgere l'esericizio? Dovrebbe essermi dato il numero complessivo di a o b o c?
Tornando all'esercizio originario io lo svolgerei nel seguente modo:
$ a^{\star}b^{\star}+(ca)+(cb) $
Potrebbe essere corretto in questo modo?
Oppure cosi:
$a^{\star}b^{\star}c^1+a+b $ ?
Il pattern quale dovrebbe essere in tal caso?
"JoKeRxbLaCk":
[...]
Tornando all'esercizio originario io lo svolgerei nel seguente modo:
$ a^{\star}b^{\star}+(ca)+(cb) $
Potrebbe essere corretto in questo modo?
Oppure cosi:
$ a^{\star}b^{\star}c^1+a+b $ ?
Il pattern quale dovrebbe essere in tal caso?
Ciao
Parto prima dall'esercizio in questione. No, entrambe le versioni non sono ancora corrette. Ricorda che il $+$ ti permette di effettuare una selezione ma non di concatenare una stringa ad un'altra. Nel primo esempio infatti è come se potessi scegliere tra quelle stringhe separate dal $+$. Il tuo secondo tentativo già si avvicina di più (e tra l'altro è una maniera per scrivere la stringa anche in modo più compatto, dato che $c$ compare sia in $ca$ che in $cb$). Manca comunque una plus di Kleene dato che si può avere almeno un'occorrenza di quelle stringhe. Quando poi hai una singola occorrenza di una lettera (vedi ad esempio $c$ nel tuo secondo tenativo, puoi omettere l'esponente, come nelle potenze tradizionali).
"JoKeRxbLaCk":
[...]
Ciao ti ringrazio per la risposta, avrei un dubbio, nel caso in cui $ a^nb^mc^l $ con $ n,m,l != 0 $ come posso svolgere l'esericizio? Dovrebbe essermi dato il numero complessivo di a o b o c?
[...]
In questo caso ti viene semplicemente richiesto che deve esserci almeno un'occorrenza per ciascuna lettera. E' un altro modo per denotare il tuo linguaggio che ovviamente è del tutto equivalente all'espressione regolare che devi determinare.
"onlyReferee":
[quote="JoKeRxbLaCk"][...]
Tornando all'esercizio originario io lo svolgerei nel seguente modo:
$ a^{\star}b^{\star}+(ca)+(cb) $
Potrebbe essere corretto in questo modo?
Oppure cosi:
$ a^{\star}b^{\star}c^1+a+b $ ?
Il pattern quale dovrebbe essere in tal caso?
Ciao
Parto prima dall'esercizio in questione. No, entrambe le versioni non sono ancora corrette. Ricorda che il $+$ ti permette di effettuare una selezione ma non di concatenare una stringa ad un'altra. Nel primo esempio infatti è come se potessi scegliere tra quelle stringhe separate dal $+$. Il tuo secondo tentativo già si avvicina di più (e tra l'altro è una maniera per scrivere la stringa anche in modo più compatto, dato che $c$ compare sia in $ca$ che in $cb$). Manca comunque una plus di Kleene dato che si può avere almeno un'occorrenza di quelle stringhe. Quando poi hai una singola occorrenza di una lettera (vedi ad esempio $c$ nel tuo secondo tenativo, puoi omettere l'esponente, come nelle potenze tradizionali).
"JoKeRxbLaCk":
[...]
Ciao ti ringrazio per la risposta, avrei un dubbio, nel caso in cui $ a^nb^mc^l $ con $ n,m,l != 0 $ come posso svolgere l'esericizio? Dovrebbe essermi dato il numero complessivo di a o b o c?
[...]
In questo caso ti viene semplicemente richiesto che deve esserci almeno un'occorrenza per ciascuna lettera. E' un altro modo per denotare il tuo linguaggio che ovviamente è del tutto equivalente all'espressione regolare che devi determinare.[/quote]
Per l'esercizio quindi sarebbe così:
$ a^{\star}b^{\star}c(a+b) $ ?
$a^\star b^\star (c (a + b))^+$. Senza il plus non riesci ad ottenere più occorrenze della stringa richiesta.
"onlyReferee":
$a^\star b^\star (c (a + b))^+$. Senza il plus non riesci ad ottenere più occorrenze della stringa richiesta.
Non riesco a capire il plus, stranamente a lezione non lo abbiamo affrontato
. Se io lo omettessi non potrei mai avere una stringa del genere: aabbca ?
Se ometti il plus puoi ottenere $abca$ ma non ad esempio $abcacaca$.
Il plus comunque non è altro che lo star in cui però non è contemplata la stringa vuota.
Il plus comunque non è altro che lo star in cui però non è contemplata la stringa vuota.
"onlyReferee":
Se ometti il plus puoi ottenere $abca$ ma non ad esempio $abcacaca$.
Il plus comunque non è altro che lo star in cui però non è contemplata la stringa vuota.
Perfetto ti ringrazio davvero tanto per l'aiuto!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo