On the state complexity of reversals of regular languages
| Autor: | Arto Salomaa, Derick Wood, Sheng Yu |
|---|---|
| Rok vydání: | 2004 |
| Předmět: |
Discrete mathematics
Finite-state machine Nested word General Computer Science Finite language Cone (formal languages) Pumping lemma for regular languages Image (mathematics) Theoretical Computer Science Reversal Combinatorics Deterministic finite automaton Regular language State complexity Nondeterminism Mirror image Mathematics Sparse language Computer Science(all) |
| Zdroj: | Theoretical Computer Science. 320(2-3):315-329 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2004.02.032 |
| Popis: | We compare the number of states between minimal deterministic finite automata accepting a regular language and its reversal (mirror image). In the worst case the state complexity of the reversal is 2n for an n-state language. We present several classes of languages where this maximal blow-up is actually achieved and study the conditions for it. In the case of finite languages the maximal blow-up is not possible but still a surprising variety of different growth types can be exhibited. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect