Induzione su stringa omega
Ciao a tutti ragazzi , come posso risolvere questo esercizio?
Si definisca per induzione l'operazione $ omega $, su stringhe dell'alfabeto {a,b,c}, che data una stringa $ alpha $ fornisce il numero di volte in cui un carattere occorre immediatamente dopo un carattere che alfabeticamente lo precede.
Io lo stavo risolvendo in questo modo:
$ omega(lambda) = 0 $
$ omega(alphax) = $ 1) $ omega(alpha) + 1 $ se (qui mi manca la condizione, non saprei come scriverla.)
__________2) $ omega(alpha) $ altrimenti.
Si definisca per induzione l'operazione $ omega $, su stringhe dell'alfabeto {a,b,c}, che data una stringa $ alpha $ fornisce il numero di volte in cui un carattere occorre immediatamente dopo un carattere che alfabeticamente lo precede.
Io lo stavo risolvendo in questo modo:
$ omega(lambda) = 0 $
$ omega(alphax) = $ 1) $ omega(alpha) + 1 $ se (qui mi manca la condizione, non saprei come scriverla.)
__________2) $ omega(alpha) $ altrimenti.
Risposte
Ciao 
Allora, innanzitutto poiché lavoriamo con una stringa in input che è finita può venirci incontro considerare la lunghezza della stringa (e non solo quella) nella condizione per il nostro caso base ed il passo induttivo.
In particolare stando alla tua versione della risoluzione bisogna che modifichi leggermente la condizione del caso base e che suddividi ulteriormente il test per il passo induttivo. Il fatto poi che abbiamo solo tre possibili caratteri in input per il nostro alfabeto ci facilita decisamente i confronti da effettuare.
Allora, innanzitutto poiché lavoriamo con una stringa in input che è finita può venirci incontro considerare la lunghezza della stringa (e non solo quella) nella condizione per il nostro caso base ed il passo induttivo.
In particolare stando alla tua versione della risoluzione bisogna che modifichi leggermente la condizione del caso base e che suddividi ulteriormente il test per il passo induttivo. Il fatto poi che abbiamo solo tre possibili caratteri in input per il nostro alfabeto ci facilita decisamente i confronti da effettuare.
"onlyReferee":
Ciao
Allora, innanzitutto poiché lavoriamo con una stringa in input che è finita può venirci incontro considerare la lunghezza della stringa (e non solo quella) nella condizione per il nostro caso base ed il passo induttivo.
In particolare stando alla tua versione della risoluzione bisogna che modifichi leggermente la condizione del caso base e che suddividi ulteriormente il test per il passo induttivo. Il fatto poi che abbiamo solo tre possibili caratteri in input per il nostro alfabeto ci facilita decisamente i confronti da effettuare.
Davvero non saprei come procedere... Come dovrei modificare il passo base?
Ovviamente con modificarlo non intendevo di certo stravolgerlo 
.
Prova a pensare (ti do il suggerimento): il fatto che una stringa sia vuota o contenga un solo elemento per noi fa la differenza (ai fini di ciò che dobbiamo calcolare voglio dire)
.Prova a pensare (ti do il suggerimento): il fatto che una stringa sia vuota o contenga un solo elemento per noi fa la differenza (ai fini di ciò che dobbiamo calcolare voglio dire)
"onlyReferee":
Ovviamente con modificarlo non intendevo di certo stravolgerlo
Prova a pensare (ti do il suggerimento): il fatto che una stringa sia vuota o contenga un solo elemento per noi fa la differenza (ai fini di ciò che dobbiamo calcolare voglio dire)
Ok
quindi:$omega(lambda) = 0$, inoltre se:
$|alpha|=1$ allora $omega(alpha) =0$
potrebbe essere corretto?
Sì. Più sinteticamente si può scrivere anche: $\omega(\alpha) = 0$ se $|\alpha| \le 1$ 
(dove $|\alpha|$ ovviamente indica la cardinalità della generica stringa in input $x$).
Ora coraggio con il passo (i due passi e già ti ho aiutato) induttivo .
(dove $|\alpha|$ ovviamente indica la cardinalità della generica stringa in input $x$).Ora coraggio con il passo (i due passi e già ti ho aiutato) induttivo
.
"onlyReferee":
Sì. Più sinteticamente si può scrivere anche: $\omega(\alpha) = 0$ se $|\alpha| \le 1$
Ora coraggio con il passo (i due passi e già ti ho aiutato) induttivo
Potrebbe essere corretta una soluzione del genere?
$omega(alphax) = $
-> se $alpha = a ^^ x = b$ allora $ omega(alpha) + 1$
-> se $alpha = b ^^ x = c$ allora $ omega(alpha) + 1$
-> altrimenti $omega(alpha)$
L'unica cosa però di questa soluzione che mi lascia perplesso è il fatto che io abbia messo tutta la stringa $alpha$ uguale ad un carattere particolare del mio alfabeto. Quindi non saprei come indicare matematicamente l'ultimo carattere di una stringa, sempre ovviamente che sia corretto il procedimento.
Se andiamo per esclusione con i casi rispetto alla lunghezza della stringa (controllo che facciamo prima di procedere al confronto dei caratteri) nulla ci vieta di analizzare solo il primo o il secondo carattere della stessa.
Comunque la tua idea del confronto è proprio quella esatta, si tratta solo di riscrivere il tutto in maniera più leggibile adesso. La tua stringa $\alpha$ è composta da più caratteri e può essere scritta come $\alpha = \alpha_1 \alpha_2 ...\alpha_{|\alpha|}$, dove $|\alpha|$ è chiaramente la lunghezza di tale stringa. Pertanto ricapitolando abbiamo:
$$
\omega(\alpha)=
\begin{cases}
0&\text{ se } |\alpha| \le 1\\
1 + \omega(\alpha_2 ...\alpha_{|\alpha|})&\text{ se } ...\\
\omega(\alpha_2 ...\alpha_{|\alpha|})&\text{ altrimenti}
\end{cases}
$$
Lascio completare la condizione del secondo "se" (i puntini che ho lasciato).
Comunque la tua idea del confronto è proprio quella esatta, si tratta solo di riscrivere il tutto in maniera più leggibile adesso. La tua stringa $\alpha$ è composta da più caratteri e può essere scritta come $\alpha = \alpha_1 \alpha_2 ...\alpha_{|\alpha|}$, dove $|\alpha|$ è chiaramente la lunghezza di tale stringa. Pertanto ricapitolando abbiamo:
$$
\omega(\alpha)=
\begin{cases}
0&\text{ se } |\alpha| \le 1\\
1 + \omega(\alpha_2 ...\alpha_{|\alpha|})&\text{ se } ...\\
\omega(\alpha_2 ...\alpha_{|\alpha|})&\text{ altrimenti}
\end{cases}
$$
Lascio completare la condizione del secondo "se" (i puntini che ho lasciato).
"onlyReferee":
Se andiamo per esclusione con i casi rispetto alla lunghezza della stringa (controllo che facciamo prima di procedere al confronto dei caratteri) nulla ci vieta di analizzare solo il primo o il secondo carattere della stessa.
Comunque la tua idea del confronto è proprio quella esatta, si tratta solo di riscrivere il tutto in maniera più leggibile adesso. La tua stringa $\alpha$ è composta da più caratteri e può essere scritta come $\alpha = \alpha_1 \alpha_2 ...\alpha_{|\alpha|}$, dove $|\alpha|$ è chiaramente la lunghezza di tale stringa. Pertanto ricapitolando abbiamo:
$$
\omega(\alpha)=
\begin{cases}
0&\text{ se } |\alpha| \le 1\\
1 + \omega(\alpha_2 ...\alpha_{|\alpha|})&\text{ se } ...\\
\omega(\alpha_2 ...\alpha_{|\alpha|})&\text{ altrimenti}
\end{cases}
$$
Lascio completare la condizione del secondo "se" (i puntini che ho lasciato).
Allora vediamo se è corretto
SE $( (alpha_{i}) = a ^^ (alpha_{i+1}) = b) vv ((alpha_{i}) = b ^^ (alpha_{i+1}) = c)))$
per $ 1 < i < |alpha| $
è corretto?
Bisogna che correggi il codice LaTeX perché deve esserci un errore. Così non si riesce a visualizzare...
"onlyReferee":
Bisogna che correggi il codice LaTeX perché deve esserci un errore. Così non si riesce a visualizzare...
Sisi infatti stavo modificando cercando di capire come fare
Il tuo $i$ in questo caso vale $1$ e di conseguenza $i + 1 = 2$. Poiché stiamo lavorando con una stringa sempre più piccola ed usiamo la ricorsione ad ogni chiamata è come se analizzassimo una nuova stringa per quello bisogna usare questi indici.
"onlyReferee":
Il tuo $i$ in questo caso vale $1$ e di conseguenza $i + 1 = 2$. Poiché stiamo lavorando con una stringa sempre più piccola ed usiamo la ricorsione ad ogni chiamata è come se analizzassimo una nuova stringa per quello bisogna usare questi indici.
Non ho ben capito... quindi è sbagliata la mia risoluzione:
SE $( (alpha_{i}) = a ^^ (alpha_{i+1}) = b) vv ((alpha_{i}) = b ^^ (alpha_{i+1}) = c)))$
per $ 1 < i < |alpha| $ ?
Basta che sostituisci $i$ con $1$, $i + 1$ con $2$ ed è corretto.
PS: le parentesi prima e dopo i singoli $\alpha$ le puoi anche omettere.
PS: le parentesi prima e dopo i singoli $\alpha$ le puoi anche omettere.
"onlyReferee":
Basta che sostituisci $i$ con $1$, $i + 1$ con $2$ ed è corretto.
PS: le parentesi prima e dopo i singoli $\alpha$ le puoi anche omettere.
Come mai dovrebbe risultare corretto in questo modo? Così facendo io non faccio il confronto sempre sul primo carattere della stringa e sul secondo? Cioè su $alpha_1$ e su $alpha_2$
È questione che stiamo lavorando per induzione e pertanto con l'uso della ricorsione. La tua osservazione sarebbe corretta soltanto se avessimo lavorato in maniera iterativa. L'esercizio però richiede espressamente di utilizzare l'induzione. Ogni volta che passi a lavorare con una porzione più piccola della stringa è come se avessi appunto una nuova stringa da analizzare senza tener conto di quanto svolto in precedenza.
Anche perché se fosse come dici te non servirebbe più scrivere il caso base come abbiamo fatto.
Anche perché se fosse come dici te non servirebbe più scrivere il caso base come abbiamo fatto.
"onlyReferee":
È questione che stiamo lavorando per induzione e pertanto con l'uso della ritorsione. La tua osservazione sarebbe corretta soltanto se avessimo lavorato in maniera iterativa. L'esercizio però richiede espressamente di utilizzare l'induzione. Ogni volta che passi a lavorare con una porzione più piccola della stringa è come se avessi appunto una nuova stringa da analizzare senza tener conto di quanto svolto in precedenza.
Anche perché se fosse come dici te non servirebbe più scrivere il caso base come abbiamo fatto.
Ok perfetto, ti ringrazio tanto!
Ho un altro problema Ovvero ho questo esercizio:
Si definisca per induzione l'operazione omega su stringhe dell'alfabeto {a,b,c}, che data una stringa alfa fornisce il numero di volte in cui un carattere è diverso da quello precedente(alternanza).
Io l'ho risolto così:
$$
\omega(\alpha)=
\begin{cases}
0&\text{ se } |\alpha| \leq 1\\
1 + \omega(\alpha)&\text{ se } \alpha_{1} \neq \alpha_{2}\\
\omega(\alpha)&\text{ altrimenti}
\end{cases}
$$
E' corretto?
Poi ne ho un altro che dice:
"Si definisca per induzione l'operazione $omega$ su stringhe dell'alfabeto {a,b,c}, che data una stinga $alpha$ fornisce il numero di volte in cui il carattere $b$ occorre in posizione dispari.
$$
\omega(\alpha)=
\begin{cases}
0&\text{ se } |\alpha| = 0\\
1 + \omega(\alpha_{1})&\text{ se } |\alpha| \bullet 2 \neq 0 \wedge \alpha_{1} = b\\
\omega(\alpha)&\text{ altrimenti}
\end{cases}
$$
Con \( \bullet \) operatore MODULO.
Ovvero ho questo esercizio:Si definisca per induzione l'operazione omega su stringhe dell'alfabeto {a,b,c}, che data una stringa alfa fornisce il numero di volte in cui un carattere è diverso da quello precedente(alternanza).
Io l'ho risolto così:
$$
\omega(\alpha)=
\begin{cases}
0&\text{ se } |\alpha| \leq 1\\
1 + \omega(\alpha)&\text{ se } \alpha_{1} \neq \alpha_{2}\\
\omega(\alpha)&\text{ altrimenti}
\end{cases}
$$
E' corretto?
Poi ne ho un altro che dice:
"Si definisca per induzione l'operazione $omega$ su stringhe dell'alfabeto {a,b,c}, che data una stinga $alpha$ fornisce il numero di volte in cui il carattere $b$ occorre in posizione dispari.
$$
\omega(\alpha)=
\begin{cases}
0&\text{ se } |\alpha| = 0\\
1 + \omega(\alpha_{1})&\text{ se } |\alpha| \bullet 2 \neq 0 \wedge \alpha_{1} = b\\
\omega(\alpha)&\text{ altrimenti}
\end{cases}
$$
Con \( \bullet \) operatore MODULO.
Nel primo le condizioni sono scritte correttamente ma non va bene parte di come è scritta la ricorsione. Scritta così la tua funzione va in un loop infinito perché se passi sempre $\alpha$ come input alla stessa ritorna a valutare di nuovo la stessa stringa e non termina più. Nel secondo branch del primo esercizio devi infatti mettere $1 + \omega(\alpha_2 ... \alpha_{|\alpha|})$ e nel terzo invece $\omega(\alpha_2 ... \alpha_{|\alpha|})$.
Riguardo al secondo esercizio. Il primo branch è corretto. Da notare che era lo stesso in questo caso se scrivevi come condizione $\alpha = \epsilon$ (ossia il caso in cui hai la stringa vuota, che è indicata spesso anche con $\lambda$). Nel secondo e nel terzo branch le condizioni sono esatte però anche qui è sbagliato l'input della ricorsione: ci va $1 + \omega(\alpha_2 ... \alpha_{|\alpha|})$ nel secondo branch e $\omega(\alpha_2 ... \alpha_{|\alpha|})$ nel terzo.
Ora di seguito ti scrivo un'altra versione del secondo esercizio che è un po' più ottimizzata perché "salta" direttamente le posizioni pari che non ci interessano nell'analisi:
$$
\omega(\alpha)=
\begin{cases}
0&\text{ se }|\alpha| = 0\\
1 + \omega(\alpha_3 ... \alpha_{|\alpha|})&\text{ se }\alpha_1 = b\\
\omega(\alpha_3 ... \alpha_{|\alpha|})&\text{ altrimenti}
\end{cases}
$$
Riguardo al secondo esercizio. Il primo branch è corretto. Da notare che era lo stesso in questo caso se scrivevi come condizione $\alpha = \epsilon$ (ossia il caso in cui hai la stringa vuota, che è indicata spesso anche con $\lambda$). Nel secondo e nel terzo branch le condizioni sono esatte però anche qui è sbagliato l'input della ricorsione: ci va $1 + \omega(\alpha_2 ... \alpha_{|\alpha|})$ nel secondo branch e $\omega(\alpha_2 ... \alpha_{|\alpha|})$ nel terzo.
Ora di seguito ti scrivo un'altra versione del secondo esercizio che è un po' più ottimizzata perché "salta" direttamente le posizioni pari che non ci interessano nell'analisi:
$$
\omega(\alpha)=
\begin{cases}
0&\text{ se }|\alpha| = 0\\
1 + \omega(\alpha_3 ... \alpha_{|\alpha|})&\text{ se }\alpha_1 = b\\
\omega(\alpha_3 ... \alpha_{|\alpha|})&\text{ altrimenti}
\end{cases}
$$
"onlyReferee":
Nel primo le condizioni sono scritte correttamente ma non va bene parte di come è scritta la ricorsione. Scritta così la tua funzione va in un loop infinito perché se passi sempre $\alpha$ come input alla stessa ritorna a valutare di nuovo la stessa stringa e non termina più. Nel secondo branch del primo esercizio devi infatti mettere $1 + \omega(\alpha_2 ... \alpha_{|\alpha|})$ e nel terzo invece $\omega(\alpha_2 ... \alpha_{|\alpha|})$.
Riguardo al secondo esercizio. Il primo branch è corretto. Da notare che era lo stesso in questo caso se scrivevi come condizione $\alpha = \epsilon$ (ossia il caso in cui hai la stringa vuota, che è indicata spesso anche con $\lambda$). Nel secondo e nel terzo branch le condizioni sono esatte però anche qui è sbagliato l'input della ricorsione: ci va $1 + \omega(\alpha_2 ... \alpha_{|\alpha|})$ nel secondo branch e $\omega(\alpha_2 ... \alpha_{|\alpha|})$ nel terzo.
Ora di seguito ti scrivo un'altra versione del secondo esercizio che è un po' più ottimizzata perché "salta" direttamente le posizioni pari che non ci interessano nell'analisi:
$$
\omega(\alpha)=
\begin{cases}
0&\text{ se }|\alpha| = 0\\
1 + \omega(\alpha_3 ... \alpha_{|\alpha|})&\text{ se }\alpha_1 = b\\
\omega(\alpha_3 ... \alpha_{|\alpha|})&\text{ altrimenti}
\end{cases}
$$
Perfetto ti ringrazio
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo