Cookes sætning om tosidede automater

Cookes sætning er et resultat af automatteori, der viser, at udførelsen af en tovejs deterministisk pushdown- automat kan simuleres i lineær tid på en hukommelsesmaskine med tilfældig adgang . Opdaget i 1970 af University of Toronto videnskabsmand Stephen Cook . Sætningen har fungeret som det teoretiske grundlag for mange lineære tekstbehandlingsalgoritmer, såsom Manaker -algoritmen , Knuth-Morris-Pratt- algoritmen og Weiner-algoritmen .

Iscenesættelse

En deterministisk pushdown-automat kan defineres som et sæt , hvor [1] $P=(Q,\Sigma,\Pi,\delta,s_{0},Z_{0},s_{t})$

$Q$ er sættet af automattilstande,
$\Sigma$ - indtast alfabet,
$\Pi$ - stak alfabet,
$\delta$ - mange overgange af automaten,
$q_{0}\in Q$ er maskinens starttilstand,
$Z$ er det nederste symbol på stakken,
${\displaystyle s_{t))$ - endelig tilstand.

Noter

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

Litteratur

Andersen N., Jones N. D. Generalizing Cooks transformation til imperative stack-programmer // Lect . Bemærk Comput. sci. / G. Goos , J. Hartmanis , J. v. Leeuwen - Berlin , Heidelberg , New York, NY , London [etc.] : Springer , 1994. - S. 1-18. — ISSN 0302-9743 ; 1611-3349 - doi:10.1007/3-540-58131-6_33
Mogensen T. Æ. WORM-2DPDA'er: En udvidelse til 2DPDA'er, der kan simuleres i lineær tid // Inform . behandle. Lett. - Elsevier BV , 1994. - Vol. 52, Iss. 1. - S. 15-22. — ISSN 0020-0190 ; 1872-6119 - doi:10.1016/0020-0190(94)90134-1
Rytter W. The Complexity of Two-Way Pushdown Automata og rekursive programmer - 1985. - S. 341-356. doi:10.1007/ 978-3-642-82456-2_24
Galil Z., Seiferas J. A Linear-Time On-Line Recognition Algorithm for ``Palstar (engelsk) // J. ACM / D. J. Rosenkrantz - New York, NY : Association for Computing Machinery , 1978. - Vol. 25, Iss. 1. - S. 102-111. — ISSN 0004-5411 ; 1557-735X - doi:10.1145/322047.322056
Jones N. D. En note om lineær tidssimulering af deterministiske tovejs pushdown-automater // Inform . behandle. Lett. - Elsevier BV , 1977. - Vol. 6, Iss. 4. - S. 110-112. — ISSN 0020-0190 ; 1872-6119 - doi:10.1016/0020-0190(77)90022-9
Manacher G. K. En ny lineær-tids "on-line" algoritme til at finde det mindste initiale palindrom af en streng // J. ACM / D. J. Rosenkrantz - New York, NY : Association for Computing Machinery , 1975. - Vol. 22, Iss. 3. - S. 346-351. — ISSN 0004-5411 ; 1557-735X - doi:10.1145/321892.321896
Apostolico A. , Breslauer D., Galil Z. Parallel detektion af alle palindromer i en streng (engelsk) // Theoretical Computer Science - Elsevier BV , 1995. - Vol. 141, Iss. 1-2. - S. 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 (engelsk) - Boston : Addison-Wesley , 1974. - 480 s. — ISBN 978-0-201-00029-0
Knuth D. E. , James H. Morris, Jr. , Pratt V. R. Fast Pattern Matching in Strings // SIAM J. Comput. / M. Sudan - SIAM , 1977. - Vol. 6, Iss. 2. - S. 323-350. — ISSN 0097-5397 ; 1095-7111 - doi:10.1137/0206024

Formelle sprog og formelle grammatikker
Generelle begreber	Chomsky hierarki Alfabet Ord
Type 0	Ubegrænset grammatik Turing maskine opregnet sprog Opløseligt sprog
Type 1	Kontekstfølsom grammatik Kontekstfølsomt sprog Lineært afgrænset automat
Type 2	Kontekstfri grammatik Tvetydig grammatik Kontekst frit sprog Pushdown-automat ( deterministisk ) Vækst Lemma Ogdens Lemma Cooks teorem
Type 3	Almindelig grammatik almindeligt sprog Almindelig udtryk Statsmaskine ( deterministisk , ikke- deterministisk ) DFA minimering Bestemmelse af NFA Myhill-Nerodes sætning
parsing	LL analysator LR-parser Rekursiv nedstigningsmetode Kok-Yngre-Kasami-algoritme