Autómata De Conteo

Autómata de conteo
Autómata finito determinista con un contador de enteros o “bolsa” en la que se colocan o extraen cuentas o “piedras” en respuesta a un símbolo de entrada. En otras palabras, encada transición el autómata no sólo selecciona un nuevo estado sino que también decide, independientemente del estado de la bolsa, si añade otra cuenta a la bolsa o saca una cuenta de la bolsa o la dejaigual. La bolsa inicia con una cuenta y el autómata continúa operando mientras haya símbolos de entrada y la bolsa no esté vacía. Si se consumen todos los símbolos de la palabra de entrada al mismotiempo que se vacía la bolsa, entonces se acepta la palabra.
A,a
A
a
a
A,a
A
a
a

Desafortunadamente los autómatas de conteo no son suficientemente poderosos para reconocer todos los LLC.
Enocasiones se requiere más de un tipo de cuenta o “roca” o en lugar de una “bolsa”.
Se utiliza un stack o pila LIFO (Last In First Out) en el cual el orden es importante. La acción que lleva a caboel autómata sólo es influenciada no sólo por el estado en que se encuentra y por el símbolo que lee, sino también por el tipo de piedra u objeto que se encuentra arriba en la pila.

palíndromos delongitud impar
Autómata de pila que acepte {wcwR | w {a, b}*}. wR es la palabra w al revés, por ejemplo, “anita”R = “atina”.
a, / A
b, / B
b, B /
a, A /
c, /
q0
q1
a, / A
b, / B
b, B/
a, A /
c, /
q0
q1

* K = {q0, q1}
* = {a, b, c}
* = {A, B}
* s0 = q0
* F = {q1}
* (q0, a, ) = (q0, A) (q1, a, A) = (q1, )
* (q0, b, ) = (q0, B) (q1,b, B) = (q1, )
* (q0, c, ) = (q1, )

palíndromos de longitud par
Autómata de pila que acepte {wwR | w {a, b}*}. wR es la palabra w al revés, por ejemplo, “anita”R = “atina”a, / A
b, / B
b,B /
a, A /
, /
q0
q1
a, / A
b, / B
b, B /
a, A /
, /
q0
q1

* K = {q0, q1}
* = {a, b}
* = {A, B}
* s0 = q0
* F = {q1}
* (q0, a, ) = (q0, A) (q1, a,...