×

zbMATH — the first resource for mathematics

Algorithmic unsolvability of the problem of recognition of recursive event representability by finite automata. (English. Russian original) Zbl 0112.35702
Autom. Remote Control 22, 646-652 (1961); translation from Avtom. Telemekh. 22, 748-755 (1961).
Two theorems on the capability of finite automata are proved. They are known to everyone acquainted with the rudiments of regular events and algorithms.
Reviewer: J. R. Büchi
MSC:
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: MNR