[A-L] (13 Febbraio 2024) Esercizio 2

[FeddyLix17]

Fila A

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

Indicare se i seguenti punti sono veri o falsi.

2. La funzione $\Large f$ è iniettiva. [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) \geq n$. [1 punto]

Fila B

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

Indicare se i seguenti punti sono veri o falsi.

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) > f(\sigma)$. [1 punto]

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

Entrambe le file

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

[FeddyLix17]

Entrambe le file

1. le funzioni binarie f della fila A e B risultano entrambe suriettive in quanto per ogni stringa binaria rappresentabile è possibile ricavare rispettivamente il numero di configurazioni di 01 o di 101 (considerando che tale quantità non può essere negativa).

---

Fila A

2. la funzione $\Large f_a$ non è iniettiva in quanto possono esistere diverse stringhe binarie con lo stesso numero di configurazioni di 01

3. Non sempre, piuttosto dovrebbe valere la proprietà

$$ \Large f_a(\sigma \tau) \begin{cases} f(\sigma) + f(\tau) \\ f(\sigma) + f(\tau) + 1 \end{cases} $$

poichè la concatenazione delle 2 stringhe $\Large \sigma$ e $\Large \tau$ potrebbe aggiungere una nuova configurazione di 01.

4. vero

5. vero, a patto che n sia sempre un numero finito

---

Fila B

2. $\Large f_b$ non è invertibile in quanto non biettiva

3. seguendo il ragionamento dello stesso punto per la fila a, falso

4. vero

5. vero , sempre a patto che n sia comunque un numero finito