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ó δ de l’autòmat: en primer lloc vénen n nombres, corresponents a les imatges dels estats amb el símbol 0: δ(0, 0), δ(1, 0), …, δ(n−1, 0). Després vénen un altres n nombres, corresponents a les imatges dels estats amb el símbol 1: δ(0, 1), δ(1, 1), …, δ(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⁹.

Observació

Resoleu aquest problema amb programació dinàmica.