Teorema de Cooke sobre autómatas de dos caras

El teorema de Cooke es el resultado de la teoría de los autómatas que demuestra que la ejecución de un autómata pushdown determinista bidireccional se puede simular en tiempo lineal en una máquina de memoria de acceso aleatorio . Descubierto en 1970 por el científico Stephen Cook de la Universidad de Toronto . El teorema ha servido como base teórica para muchos algoritmos de procesamiento de texto lineal, como el algoritmo de Manaker , el algoritmo de Knuth-Morris-Pratt y el algoritmo de Weiner .

Puesta en escena

Un autómata pushdown determinista se puede definir como un conjunto , donde [1] $P=(Q,\Sigma ,\Pi ,\delta ,s_{0},Z_{0},s_{t})$

$q$ es el conjunto de estados del autómata,
$\Sigma$ - alfabeto de entrada,
$\Pi$ - alfabeto de pila,
$\delta$ - muchas transiciones del autómata,
$q_{0}\en Q$ es el estado inicial de la máquina,
$Z$ es el símbolo inferior de la pila,
${\ Displaystyle s_ {t}}$ - estado final.

Notas

↑ Aho, Hopcroft, Ullman, 1974 , pág. 337

Literatura

Andersen N., Jones N. D. Generalización de la transformación de Cook a programas de pila imperativa // Lect . Nota Cómputo. ciencia / G. Goos , J. Hartmanis , J. v. Leeuwen - Berlín , Heidelberg , Nueva York, NY , Londres [etc.] : Springer , 1994. - P. 1-18. — ISSN 0302-9743 ; 1611-3349 - doi:10.1007/3-540-58131-6_33
Mogensen T. Æ. WORM-2DPDAs: Una extensión de 2DPDAs que se puede simular en tiempo lineal // Informar . proceso. Letón. - Elsevier BV , 1994. - Vol. 52, edición. 1.- Pág. 15-22. — ISSN 0020-0190 ; 1872-6119 - doi:10.1016/0020-0190(94)90134-1
Rytter W. La complejidad de los autómatas pushdown bidireccionales y los programas recursivos - 1985. - S. 341-356. doi:10.1007/ 978-3-642-82456-2_24
Galil Z., Seiferas J. Un algoritmo de reconocimiento en línea de tiempo lineal para ``Palstar (inglés) // J. ACM / D. J. Rosenkrantz - Nueva York, NY : Association for Computing Machinery , 1978. - Vol. 25, edición. 1.- Pág. 102-111. — ISSN 0004-5411 ; 1557-735X - doi:10.1145/322047.322056
Jones N. D. Una nota sobre la simulación de tiempo lineal de autómatas pushdown bidireccionales deterministas // Inform . proceso. Letón. - Elsevier BV , 1977. - Vol. 6, edición. 4.- Pág. 110-112. — ISSN 0020-0190 ; 1872-6119 - doi:10.1016/0020-0190(77)90022-9
Manacher G. K. Un nuevo algoritmo "en línea" de tiempo lineal para encontrar el palíndromo inicial más pequeño de una cadena // J. ACM / D. J. Rosenkrantz - Nueva York, NY : Association for Computing Machinery , 1975. - Vol. 22, edición. 3.- Págs. 346-351. — ISSN 0004-5411 ; 1557-735X - doi:10.1145/321892.321896
Apostolico A. , Breslauer D., Galil Z. Detección paralela de todos los palíndromos en una cadena (inglés) // Ciencias informáticas teóricas - Elsevier BV , 1995. - Vol. 141, edición. 1-2. - Pág. 163-173. — ISSN 0304-3975 ; 1879-2294 - doi:10.1016/0304-3975(94)00083-U
Aho A. , Hopcroft J. E. , Ullman J. D. Diseño y análisis de algoritmos informáticos (inglés) - Boston : Addison-Wesley , 1974. - 480 p. — ISBN 978-0-201-00029-0
Knuth D.E. , James H. Morris, Jr. , Pratt V. R. Coincidencia rápida de patrones en cadenas // SIAM J. Comput. / M. Sudán - SIAM , 1977. - Vol. 6, edición. 2.- Pág. 323-350. — ISSN 0097-5397 ; 1095-7111 - doi:10.1137/0206024

Lenguajes formales y gramáticas formales
Conceptos generales	Jerarquía de Chomsky Alfabeto Palabra
tipo 0	Gramática ilimitada máquina de Turing lenguaje enumerado Lenguaje resoluble
Tipo 1	Gramática sensible al contexto Lenguaje sensible al contexto Autómata linealmente acotado
Tipo 2	gramática libre de contexto gramática ambigua lenguaje libre de contexto Autómata pushdown ( determinista ) Lema de crecimiento Lema de Ogden teorema de Cook
tipo 3	gramática regular lenguaje normal Expresión regular Máquina de estados ( determinista , no determinista ) minimización de DFA Determinación de NFA Teorema de Myhill-Nerode
analizando	analizador LL analizador LR Método de descenso recursivo Algoritmo Kok-Younger-Kasami