Diseñar un autómata finito comprobando la división del número de caracteres

Question

Necesito diseñar y dibujar un autómata finito que pueda aceptar las letras {a,b} .

El número de las letras a debe dividirse por 3, y el número de la letra b debe dividirse por 2.

Por ejemplo, los autómatas deberían aceptar las siguientes muestras:

aaabb, baaba, bbaaabaaba

Gracias de antemano.

Answer 1

Pista:

Es una tarea muy bonita, así que sólo daré esta pequeña ayuda.

• Sólo se trata de palabras de $L=\{a,b\}^*$
• ¿Qué FA aceptaría las palabras con un número de $a$ símbolos divisibles por $3$ ?
• ¿Qué FA aceptaría las palabras con un número de $b$ símbolos divisibles por $2$ ?
• ¿Cómo se podría construir una FA que combine ambas FA anteriores? ¿Cómo se combinarían los estados y estados finales de la primera con los estados y estados finales de la segunda AF para obtener estados y estados finales para la AF combinada?

Answer 2

SUGERENCIA: Utiliza los estados para controlar el número de $a$ s módulo $2$ y el número de $b$ s módulo $3$ . Es decir, utilizar los estados $q_{0,0},q_{0,1},q_{0,2},q_{1,0},q_{1,1}$ y $q_{1,2}$ y diseñar el autómata de forma que se encuentre en el estado $q_{i,j}$ cuando el número de $a$ s es de la forma $2m+i$ y el número de $b$ s es de la forma $2n+j$ para algunos enteros no negativos $m$ y $n$ .

• ¿Cómo deben ser las transiciones?
• ¿Cuál de estos estados debe ser el estado inicial?
• ¿Qué estado(s) debe(n) ser aceptor(es)?