Timeline for A special class of regular languages: "circular" languages. Is it known?
Current License: CC BY-SA 2.5
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 27, 2011 at 21:02 | comment | added | Benjamin Steinberg | Oops, I read the statement too quickly. The iff made me think he wanted that some power of w in the language implies w in the language. In other words, I thought he want pure + closed under powers. The iff statement is not really needed then. He wants the implication $w\in L$ implies $w^+\subseteq L$. So Yuval's answer is perfect. Sorry. | |
| Jun 23, 2011 at 14:47 | comment | added | LSpice | @Benjamin Steinberg, why is this language not circular? The obvious thought (to me) is that the condition would require $a \in L$, but it doesn't really …. | |
| Jun 23, 2011 at 1:33 | comment | added | Benjamin Steinberg | @Yuval, he asks that $w$ belongs to $L$ iff $w^k\in L$ for all positive $k$. Thus the language of all even powers of the letter $a$ is not circular in his sense although it is $(a^2)^*$. | |
| Jan 12, 2011 at 20:40 | comment | added | Dylan Thurston | Sorry, I was indeed premature. I'll try to fix this later. The right characterization should be using r+ rather than r*. | |
| Jan 12, 2011 at 16:37 | comment | added | Yuval Filmus | In fact, a language is circular iff it's the <i>union</i> of expressions of the form $r^*$. | |
| Jan 12, 2011 at 13:47 | comment | added | Łukasz Grabowski | Dylan: Are you sure L is circular iff L=M*? The example I have in mind is a langauge on letters <a,b> consisting only of powers of a and of powers of b. AFAIU it is circular, but I can't see why it's M* for some M. | |
| Jan 12, 2011 at 9:36 | comment | added | Neel Krishnaswami | The automata construction you suggest always admits the empty string, but he required that $w^k \in L$ for $k > 0$, not $k \geq 0$. So $a+$ would be circular according to his definition, but its minimal automaton would not share accept and start states. | |
| Jan 12, 2011 at 8:00 | history | answered | Dylan Thurston | CC BY-SA 2.5 |