Teorema lui Cooke asupra automatelor cu două fețe

Teorema lui Cooke este un rezultat al teoriei automatelor care demonstrează că execuția unui automat pushdown determinist în două sensuri poate fi simulată în timp liniar pe o mașină de memorie cu acces aleatoriu . Descoperit în 1970 de omul de știință Stephen Cook de la Universitatea din Toronto . Teorema a servit drept bază teoretică pentru mulți algoritmi de procesare liniară a textului, cum ar fi algoritmul Manaker , algoritmul Knuth-Morris-Pratt și algoritmul Weiner .

Montare

Un automat determinist pushdown poate fi definit ca un set , unde [1] $P=(Q,\Sigma,\Pi,\delta,s_{0},Z_{0},s_{t})$

$Q$ este setul de stări automate,
$\Sigma$ - introducerea alfabetului,
$\Pi$ - stivă alfabet,
$\delta$ - multe tranziții ale automatului,
$q_{0}\in Q$ este starea inițială a mașinii,
$Z$ este simbolul de jos al stivei,
$s_{t)$ - starea finală.

Note

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

Literatură

Andersen N., Jones N. D. Generalizing Cook's transformation to imperative stack programs // Lect . Notă Comput. sci. / G. Goos , J. Hartmanis , J. v. Leeuwen - Berlin , Heidelberg , New York, NY , Londra [etc.] : Springer , 1994. - P. 1-18. — ISSN 0302-9743 ; 1611-3349 - doi:10.1007/3-540-58131-6_33
Mogensen T. Æ. WORM-2DPDA-uri: O extensie la 2DPDA-uri care poate fi simulată în timp liniar // Informați . proces. Lett. - Elsevier BV , 1994. - Vol. 52, Iss. 1. - P. 15-22. — ISSN 0020-0190 ; 1872-6119 - doi:10.1016/0020-0190(94)90134-1
Rytter W. The Complexity of Two-Way Pushdown Automata and Recursive Programs - 1985. - S. 341-356. doi:10.1007/ 978-3-642-82456-2_24
Galil Z., Seiferas J. Un algoritm de recunoaștere on-line în timp liniar pentru ``Palstar (Engleză) // J. ACM / D. J. Rosenkrantz - New York, NY : Association for Computing Machinery , 1978. - Vol. 25, Iss. 1. - P. 102-111. — ISSN 0004-5411 ; 1557-735X - doi:10.1145/322047.322056
Jones N. D. O notă despre simularea în timp liniară a automatelor pushdown deterministe în două sensuri // Informați . proces. Lett. - Elsevier BV , 1977. - Vol. 6, Iss. 4. - P. 110-112. — ISSN 0020-0190 ; 1872-6119 - doi:10.1016/0020-0190(77)90022-9
Manacher G. K. Un nou algoritm „on-line” în timp liniar pentru găsirea celui mai mic palindrom inițial al unui șir // J. ACM / D. J. Rosenkrantz - New York, NY : Association for Computing Machinery , 1975. - Vol. 22, Iss. 3. - P. 346-351. — ISSN 0004-5411 ; 1557-735X - doi:10.1145/321892.321896
Apostolico A. , Breslauer D., Galil Z. Parallel detection of all palindromes in a string (engleză) // Theoretical Computer Science - Elsevier BV , 1995. - Vol. 141, Iss. 1-2. - P. 163-173. — ISSN 0304-3975 ; 1879-2294 - doi:10.1016/0304-3975(94)00083-U
Aho A. , Hopcroft J. E. , Ullman J. D. The Design and Analysis of Computer Algorithms (engleză) - Boston : Addison-Wesley , 1974. - 480 p. — ISBN 978-0-201-00029-0
Knuth D. E. , James H. Morris, Jr. , Pratt V. R. Potrivirea rapidă a modelelor în șiruri // SIAM J. Comput. / M. Sudan - SIAM , 1977. - Vol. 6, Iss. 2. - P. 323-350. — ISSN 0097-5397 ; 1095-7111 - doi:10.1137/0206024

Limbi formale și gramatici formale
Concepte generale	Ierarhia Chomsky Alfabet Cuvânt
Tip 0	Gramatică nelimitată mașină Turing limbaj enumerat Limbajul rezolvabil
Tipul 1	Gramatică sensibilă la context Limbaj sensibil la context Automat delimitat liniar
Tipul 2	Gramatică fără context Gramatică ambiguă Limbaj fără context Automat Pushdown ( determinist ) Lema de creștere Lema lui Ogden Teorema lui Cook
Tip 3	Gramatica obișnuită limbaj obișnuit Expresie uzuala Mașină de stări ( deterministă , nedeterministă ) Minimizarea DFA Determinarea NFA Teorema Myhill-Nerode
analizare	Analizor LL Analizor LR Metoda coborârii recursive Algoritmul Kok-Younger-Kasami