| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428911 | Information Processing Letters | 2006 | 4 Pages |
Abstract
We show that if M is a DFA with n states over an alphabet with at least two letters and L=L(M), then the worst-case state complexity of L2 is nn2−2n−1. If, however, M is a DFA over a unary alphabet, then the worst-case state complexity of Lk is kn−k+1 for all k⩾2.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
