Autòmats finits deterministes X52431

Donat un autòmat finit determinista sobre l’alfabet binari i un nombre natural $m$, volem calcular el nombre de paraules de longitud $0$, $1$, $2$, ..., $m$ acceptades per l’autòmat.

Per exemple, considerem l’autòmat següent:

Hi ha tres estats $0$, $1$ i $2$, dels quals només l’estat $0$ és d’acceptació. L’estat $0$ és també l’estat inicial.

Aleshores:

• De longitud $0$ hi ha una única paraula acceptada, la paraula buida.

• De longitud $1$ només s’accepta la paraula $0$.

• De longitud $2$ només s’accepten les paraules $00$ i $11$.

• De longitud $3$ només s’accepten les paraules $000$, $011$ i $110$.

• De longitud $4$ només s’accepten les paraules $0000$, $0011$, $0110$, $1001$, $1100$ i $1111$.

(de fet, es pot veure que el llenguatge d’aquest autòmat són els múltiples de $3$, representats en binari)

De manera que si $m=4$ aleshores la sortida hauria de consistir en els nombres $1$, $1$, $2$, $3$, $6$.

Entrada

L’entrada comença amb $n$, el nombre d’estats de l’autòmat finit, que es representen amb nombres naturals entre $0$ i $n-1$. A continuació es descriu la funció de transició $\delta$ de l’autòmat: en primer lloc vénen $n$ nombres, corresponents a les imatges dels estats amb el símbol $0$: $\delta(0, 0)$, $\delta(1, 0)$, …, $\delta(n-1, 0)$. Després vénen un altres $n$ nombres, corresponents a les imatges dels estats amb el símbol $1$: $\delta(0, 1)$, $\delta(1, 1)$, …, $\delta(n-1, 1)$. A continuació vénen $n$ zeros i uns, que indiquen per cada estat $0$, …, $n-1$ si és d’acceptació (1) o no (0). L’estat inicial sempre és l’estat 0. Finalment l’entrada acaba amb el nombre $m$, la màxima longitud que es vol considerar.

Sortida

Per cada valor $l$ entre $0$ i $m$, escriviu el nombre de paraules acceptades per l’autòmat de longitud $l$. Es garanteix que tots els nombres són més petits que $10^{9}$.

Observació

Resoleu aquest problema amb programació dinàmica.