Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10334372 | Theoretical Computer Science | 2005 | 7 Pages |
Abstract
Conversely, for 2m⩽n, the class of languages (m,n)-recognizable by deterministic finite automata is uncountable for a two-letter alphabet. When restricted to a one-letter alphabet, then every (m,n)-recognizable language is regular. This was also shown by Kinber. We give a new and more direct proof for this result.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Holger Austinat, Volker Diekert, Ulrich Hertrampf, Holger Petersen,