On the state complexity of reversals of regular languages

被引：67

作者：

Salomaa, A

Wood, D

Yu, S ^{[1
]}

机构：

[1] Univ Western Ontario, Dept Comp Sci, Middlesex Coll 383, London, ON N6A 5B7, Canada

[2] Hong Kong Univ Sci & Technol, Dept Comp Sci, Kowloon, Hong Kong, Peoples R China

[3] Turku Ctr Comp Sci, Turku 20520, Finland

来源：

THEORETICAL COMPUTER SCIENCE | 2004年 / 320卷 / 2-3期

关键词：

state complexity; nondeterminism; reversal; mirror image; finite language;

D O I：

10.1016/j.tcs.2004.02.032

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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 2(n) 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. (C) 2004 Elsevier B.V. All rights reserved.

引用

页码：315 / 329

页数：15

共 8 条

[1]

Brzozowski J., 1962, MATH THEORY AUTOMATA, V12, P529

[2]

CAMPEANU C, LECT NOTES COMPUTER, V2214, P60

[3] SUCCINCT REPRESENTATION OF REGULAR LANGUAGES BY BOOLEAN AUTOMATA [J].