Autòmats Finits P26055

Un autòmat finit és un graf dirigit tal que de cadascun dels vèrtexs (anomenats estats) en surten dos arcs (anomenades transicions), amb etiquetes 0 i 1. Hi ha un estat anomenat inicial. A més, els estats poden ser d’acceptació o de rebuig. Per exemple, a l’autòmat

l’estat inicial és el 0, i hi ha un únic estat d’acceptació, el 4.

Donada una paraula amb zeros i uns, l’autòmat accepta la paraula si, des de l’estat inicial, llegint la paraula d’esquerra a dreta i saltant d’estat a estat seguint la transició del símbol actual, al final s’acaba en un estat d’acceptació.

Per exemple, considerem la paraula 0100: comencem al 0, amb el 0 anem a 1, amb el 1 anem a 2, amb el 0 anem a 3, i finalment amb el 0 acabem a 4, que és d’acceptació, així que la paraula és acceptada. En canvi, tots els prefixos de 0100 (això és, la paraula buida, 0, 01 i 010) són rebutjats, perquè després de llegir-los l’estat al que s’acaba és de rebuig. De fet, 0100 és la paraula més curta de les acceptades per aquest autòmat (que són precisament totes les que contenen 0100).

Donat un autòmat finit, podeu determinar la paraula més curta acceptada (si n’hi ha cap)?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb el nombre d’estats n, els quals es representen amb nombres entre 0 i n − 1. A continuació vénen n ‍parells s₀ s₁, un per a cada estat 0 ≤ i < n, indicant una transició entre i i s₀ etiquetada amb un 0, i una transició entre i i s₁ etiquetada amb un 1, respectivament. Finalment ve una paraula amb n caràcters, que indiquen per a cada estat 0, …, n−1 si és d’acceptació ‘A’ o de rebuig ‘R’. Assumiu 2 ≤ n ≤ 10⁴, que l’estat inicial sempre és el 0, que sempre serà de rebuig, i que almenys hi ha un estat d’acceptació.

Sortida

Per cada cas, escriviu la paraula més curta acceptada per l’autòmat. En cas d’empat, trieu la paraula lexicogràficament més petita. Si no n’hi ha cap, escriviu “no”.