Timeline for Find non-regular $L$ such that $L \cup L^R$ is regular?

12 events

when toggle format	what		by	license	comment
Nov 1, 2012 at 23:00	comment	added	Cat		@Raphael That's a much better way of phrasing it, heh. I'll be sure to pass that on to him. :)
Nov 1, 2012 at 22:34	comment	added	Raphael		$\langle M \rangle$ is an encoding of the Turing machine $M$ into a string. To your professor I say, "$\{w^k \mid w \in \{a,b\}^, k \in \mathbb{N}\}$?" Or, in other words: the number of repetitions is irrelevant, the complexity of the language lies in repetition*.
Nov 1, 2012 at 17:29	comment	added	Cat		@Raphael That's fair, though I'm not entirely familiar with the second one's syntax. My professor would also probably say the first one uses counting, since it's "some indeterminable string repeated exactly twice."
Nov 1, 2012 at 17:19	comment	added	Raphael		That depends of what you consider to be "counting". Consider $\{ww \mid w \in \{a,b\}^*\}$ and $\{\langle M \rangle \mid M\ \ TM, M(0) = 0\}$ which are both not regular.
Nov 1, 2012 at 17:10	vote	accept	Cat
Nov 1, 2012 at 17:07	comment	added	Cat		@Raphael Are there non-regular languages that do not require counting? I'm not aware of any.
Nov 1, 2012 at 14:28	history	edited	Raphael		edited tags
Nov 1, 2012 at 14:27	comment	added	Raphael		"L must involve some kind of counting." -- how so?
Nov 1, 2012 at 12:33	answer	added	Vor		timeline score: 8
Nov 1, 2012 at 6:58	history	tweeted			twitter.com/#!/StackCompSci/status/263897843213938688
Nov 1, 2012 at 6:49	answer	added	Ran G.		timeline score: 9
Nov 1, 2012 at 5:15	history	asked	Cat	CC BY-SA 3.0