[A-L] (12 Giugno 2023) Esercizio 2

[FeddyLix17]

Sia $\Large f$ la funzione che associa a una stringa finita binaria (ossia una successione finita ordinata di 0 e di 1) il massimo numero di 1 consecutivi nella stringa.

Indicare se i seguenti punti sono veri o falsi.

1. La funzione $\Large f$ è iniettiva. [1 punto]

2. La funzione $\Large f$ è invertibile. [1 punto]

3. Se $\Large \sigma$ e $\Large \tau$ sono due stringhe finite binarie e $\Large \sigma \tau$ è la loro concatenazione, vale $\Large f(\sigma \tau ) = f(\sigma) + f(\tau)$. [1 punto]

4. Con la notazione del punto precedente, per ogni stringa $\Large \sigma$, vale $\Large f(\sigma \sigma) \geq f(\sigma)$. [1 punto]

5. Per ogni $\Large n \geq 1$ esiste una stringa $\Large \sigma$ tale che $\Large f(\sigma) < n$. [1 punto]

[FeddyLix17]

1. falso, diverse stringhe binarie possono avere lo stesso massimo numero di 1 consecutivi

2. falso, poichè non iniettiva

3. falso, vale $\Large f(\sigma \tau ) \geq f(\sigma) + f(\tau)$

4. vero

5. vero (finchè n rimane un numero finito)