Hipótesis (regularidad del lenguaje) y algoritmo (L-graph a NFA) en TOC

Requisito previo: autómatas finitos , gráficos L y lo que representan
Los gráficos L pueden generar lenguajes sensibles al contexto, pero es mucho más difícil programar un lenguaje sensible al contexto que programar uno normal. Es por eso que se me ocurrió una hipótesis sobre qué tipo de L-graphs pueden generar un lenguaje regular. Pero primero, necesito presentarles lo que llamo un nido iterativo.

Como puede recordar, un nido es un camino neutral $T_1T_2T_3$ , donde $T_1$ y $T_3$ son ciclos y $T_2$ el camino es neutral. Llamaremos a $T_1T_2T_3$ un nido iterativo, si $T_1$ y $T_2$ las $T_3$ rutas imprimen la misma string de símbolos varias veces, para ser más exactos $T_1$ imprime $\alpha^k$ , $T_2$ imprime $\alpha^l$ , $T_3$ imprime $\alfa^m$ , $k, \: l, \: m \geqslant 0$ y $\alfa$ es una string de símbolos de entrada (mejor, si al menos uno de $k, \: l\: y\: m\: es \geqslant 1$ ).
De esta definición surge la siguiente hipótesis.

Hipótesis: si en un L-grafo G libre de contexto todos los nidos están iterando, entonces el lenguaje definido por este L-grafo G, L(G), es regular.
Si esta hipótesis se prueba en un futuro cercano, puede cambiar mucho en la programación que hará que la creación de nuevos lenguajes de programación sea mucho más fácil de lo que ya es. La hipótesis anterior conduce al siguiente algoritmo de conversión de gráficos L libres de contexto con nidos iterativos en un NFA.

Algoritmo – Conversión de un gráfico L libre de contexto con complementos iterativos a un NFA correspondiente
Entrada – Gráfico L libre de contexto $G=(\Sigma, V, P, \lambda, P_0, F)$ con complementos iterativos
Salida – $G'=(\Sigma', V', \lambda', P'_0, F')\\*$

Paso 1: Los idiomas de L-graph y NFA deben ser los mismos, por lo tanto, no necesitaremos un nuevo alfabeto $\Rightarrow \Sigma'' = \Sigma, \: P'' = P$ . (Comentario: construimos el L-grafo G» libre de contexto, que es igual al gráfico de inicio G’, sin nidos en conflicto)
Paso 2: Construya Core(1, 1) para el gráfico G.
V» := {(v, $\varepsilon$ ) | v $\en$ V del $\para todos$ canon k $\en$ Núcleo (1, 1), v $\no en$ k}
$\lambda''$ := { arcos $o \in \lambda$ | estados inicial y final $o', o'' \en$ V»}
Para todos los k $\en$ Core(1, 1):
Paso 1′. v := 1er estado del canon k. $\eta:= \varepsilon$ .
V» $\taza= (v, \eta)$
Paso 2′. $\lambda'' \taza=$ el arco del estado $(v, \eta)$ siguió este arco al nuevo estado definido con las siguientes reglas:
$\eta := \eta$ , si el paréntesis de entrada en este arco $= \varepsilon$ ; $\eta'la\:entrada\:corchete'$ , si el paréntesis de entrada es de apertura; $\eta 'sin\: el\: último\: paréntesis'$ , si el corchete de entrada es un corchete de cierre
v := 2do estado del canon k
V» $\taza= (v, \eta)$
Paso 3′. Repita el Paso 2′, mientras todavía haya arcos en el canon.
Paso 3: Construir Núcleo (1, 2).
Si el canon tiene 2 arcos iguales seguidos: el estado inicial y el estado final coinciden; agregamos el arco del estado dado en sí mismo, usando este arco, a $\lambda''$ .
Agregue el resto en $\lambda$ arcos v – u $(\alfa)$ to $\lambda''$ en forma de $(v, \varepsilon) - (u, \varepsilon) (\alfa)$
Paso 4: $P''_0 = (P_0, \varepsilon).\: F'' = \{(f, \varepsilon) | f\en F\}$
(Comentario: el siguiente es un algoritmo para convertir L-graph G» libre de contexto en NFA G’)
Paso 5: haga lo siguiente para cada complemento iterativo $T = T_1T_2T_3$ en G»:
agregue un nuevo estado v. Cree una ruta que comience en el estado $beg(T_3)$ , igual a $T_3$ . Desde v hasta $T_3$ crear la ruta, igual a $T_1$ . Eliminar ciclos $T_1$ y $T_3$ .
Paso 6: G’ = G», donde los arcos no se cargan con corchetes.

Para que todos los pasos anteriores queden claros, les muestro el siguiente ejemplo.
$\textbf{Example:}\\ \textbf{Input:}$ Gráfico L libre de contexto con complementos iterativos
$G = ( \{a, b, c\}, \\*\{1, 2, 3\} \\*\{( (, ) ), ( [, ] )\}, \\*\\*\{ (: \{ 1 - a - 1 \}, \\*): \{ 2 - a - 2 \}, \\*\big[: \{ 1 - b - 2 \}, \\*\big]: \{ 2 - c - 3 \}, \\*\varepsilon: \{ 1 - a - 2 \} \}, \\*\\*1, \\*\{2, 3\} \}$ ,
que determina el $language = \{a^(^2^n^+^1^) | n \geqslant 0\} \cup \{bc\}$
gráfico de inicio G
$\Sigma'' = \{a, b, c\}\\ V'' = \varnothing\\ \lambda'' = \varnothing$
Core(1, 1) = { 1 – a – 2 ; 1 – a, (1 – 1 – a – 2 – a, )1 – 2 ; 1 – b, (2 – 2 – c, )2 – 3 }
Núcleo(1, 2) = Núcleo(1, 1) $\cup$ { 1 – a, (1 – 1 – a, (1 – 1 – a – 2 – a, )1 – 2 – a, )1 – 2 }
Paso 2: Paso 1′ – Paso 3′
$\Rightarrow\\ V'' = \{(1, \varepsilon), (2, (_2), (3, \varepsilon), (1, (_1), (2, )_1), (2, \varepsilon)\}\\* \lambda'' = \{ \\*(: \{ (1, \varepsilon) - a - (1,(); (1,() - a - (1,() \}, \\*): \{ (2, )) - a - (2, )); (2, )) - a - (2, \varepsilon) \}, \\*\big[: \{ (1, \varepsilon) - b - (2, [) \}, \\*\big]: \{ (2, [) - c - (3, \varepsilon) \}, \\*\varepsilon: \{ (1, \varepsilon) - a - (2, \varepsilon); (1,() - a - (2, )) \} \}\\ P''_0 = (1, \varepsilon)\\ F'' = \{(2, \varepsilon), (3, \varepsilon)\}\\ G'' = (\Sigma'', V'', P'', \lambda'', P''_0, F'')$
Gráfico intermedio G»
$\Sigma' = \{a, b, c\}\\ V' = V'' \cup \{4\}\\ P'_0 = P''_0\\ F' = F''\\ \lambda' = \{ \\*(1, \varepsilon) - a - (1,(); \\*(2, )) - a - 4; \\*4 - a - (2, )); \\*(2, )) - a - (2, \varepsilon); \\*(1, \varepsilon) - b - (2, [); \\*(2, [) - c - (3, \varepsilon); \\*(1, \varepsilon) - a - (2, \varepsilon); \\*(1,() - a - (2, )) \}\\ G' = (\Sigma', V', \lambda', P'_0, F')$
NFA G’

Publicación traducida automáticamente

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

Deja una respuesta Cancelar la respuesta