(difs.) ← Revisión anterior | Revisión actual (difs.) | Revisión siguiente → (difs.)
Demostrar Verdadero o Falso
a) Si es AFD completo y mínimo entonces es AFD completo y mínimo también.
b) Sea .
Para cada AFD con un estado trampa y completo sea AFD tal que
- ,
- , para todo y ,
- ,
- .
Si es mínimo entonces también.
Un autómata contador es un autómata de pila con un alfabeto de pila de solamente dos símbolos, el inicial (que representa el cero), y el que se usa para contar en un unario. Cada transición incrementa el contador en uno, o lo decrementa en uno, o lo deja igual. En cada transición se puede consultar si el contador es cero o no (tope de la pila).
Demostrar Verdadero o Falso
a) Si un lenguaje es reconodible por un autómata contador entonces el lenguaje complemento también.
b) Si dos lenguajes y reconocibles por autómatas contadores entonces el lenguaje de su unión también.
c) Si dos lenguajes y reconocibles por autómatas contadores entonces el lenguaje de su intersección también.