Introducción a los autómatas de cola

Ya conocemos Finite Automata que se puede usar para aceptar lenguajes regulares y Pushdown Automata que se pueden usar para reconocer Context Free Languages.

Queue Automata (QDA) es un autómata no determinista que es similar a Pushdown Automata pero tiene una cola en lugar de una pila que ayuda a Queue automata a reconocer idiomas más allá de los idiomas libres de contexto.

Un QDA es una tupla de 6 $M = (Q, \sigma, \Gamma, \delta, q_0, F)$

Dónde

Q es el conjunto de estados finitos.
$\bf{\sigma}$ es el conjunto de alfabetos de entrada finitos.
$\bf{\Gamma}$ es el conjunto de alfabetos de cola finitos.
$\delta : Q \times \sigma_\epsilon \times \Gamma_\epsilon \rightarrow P(Q \times \Gamma_\epsilon )$ .
$q_0 \in Q$ es el estado inicial.
F $\subseteq$ Q es el conjunto de estados de aceptación.

Aceptación de una string

Un QDA $M = (Q, \sigma, \Gamma, \delta, q_0, F)$ acepta entrada $w$ si $w$ se puede escribir como $w= w_1w_2w_3 ... . w_m$ , donde cada uno $w_i \in$ $\sigma_\epsilon$ de ellos existen estados $r_0, r_1, r_2, ... . ., r_m \in Q$ y strings $s_0, s_1, s_2, ... . ., s_m \in \Gamma^*$ , de modo que satisfagan las siguientes condiciones:

$r_0 = q_0$ y $s_0 = \epsilon$ .
para $0\leq i \leq m-1$ $( r_{i+1}, b) = \delta(r_i, w_{i+1}, a), where\, a, b \in \Gamma_\epsilon$ y $s_i = ta$ y $s_{i+1} = bt$ y $t \in \Gamma^*$
$r_m \in F$

Ejemplo:
definir los autómatas de cola para el idioma ${a^nb^n | n \geq 0}$

Solución:
Q = {q0, q1, q2, q3} and $\sigma$ ={a, b} and $\Gamma$ = {a, b, $}
Y las funciones de transición están dadas por:
$\delta(q0, a, \epsilon)={(q0, a)}$
$\delta(q0, \epsilon, \epsilon)={(q1, \$)}$
$\delta(q1, \epsilon, a)={(q2, \epsilon)}$
$\delta(q2, \epsilon, a)={(q2, a)}$
$\delta(q2, b, \$)={(q1, \$)}$
$\delta(q1, \epsilon, \$)={(q3, \$)}$

Veamos cómo funciona este autómata para aabb.

Fila	Estado	Aporte	Función de transición	Cola (Entrada desde la izquierda)	Estado después del movimiento
1	q0	un abb	δ(q0, a, ε)={(q0, a)}	a	q0
2	q0	un un bb	δ(q0, a, ε)={(q0, a)}	Automóvil club británico	q0
3	q0	ε	δ(q0, ε, ε)={(q1, $)}	$aaa	q1
4	q1	ε	δ(q1, ε, a)={(q2, ε)}	$a	q2
5	q2	ε	δ(q2, ε, a)={(q2, a)}	un $	q2
6	q2	aa b b	δ(q2, b, $)={(q1, $)}	$a	q1
7	q1	ε	δ(q1, ε, a)={(q2, ε)}	ps	q2
8	q2	aab b	δ(q2, b, $)={(q1, $)}	ps	q1
9	q1	ε	δ(q1, ε, $)={(q3, $)}	ps	q3

Publicación traducida automáticamente

Artículo escrito por mayankjoshi0841 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta Cancelar la respuesta