|
|||||
|
|
Squares of regular languages |
|
| Authors: | Gerhard Lischke |
| Abstract: | The square of a language L is the set of all words pp where p ∈ L. The square of a regular language may be regular too or context‐free or none of both. We give characterizations for each of these cases and show that it is decidable whether a regular language has one of these properties. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim) |
| Keywords: | Regular languages context‐free languages primitive words decidability |