Definition talk:Regular Expression

“only contains those words”

I am not sure what is meant by:

$L(R)$ only contains those words.

I could just refer to Definition:Kleene Closure if that is preferred, but I don’t the problem with the current definition.

For reference, the definition says:

if $w_1 \in L\left({R}\right)$ and $w_2 \in L\left({R_1}\right)$, then $w_1 w_2 \in L\left({R}\right)$

and not:

if $w_1 \in L\left({R_1}\right)$ and $w_2 \in L\left({R_1}\right)$, then $w_1 w_2 \in L\left({R}\right)$.

You are not excluding that $L(R)$ is larger than what you defined it to contain. --Lord_Farin (talk) 17:48, 20 December 2012 (UTC)

Oooh. I thought that was a given. OK, I’ll add that. — Timwi (talk) 17:49, 20 December 2012 (UTC)

Hang on, by the same logic, isn’t the definition of regular expression itself vulnerable to that criticism? It doesn’t explicitly exclude that pink sheep aren’t also regular expressions. The same goes for the definition of primitive recursive function that I learnt (but yours does have the restriction). — Timwi (talk) 17:52, 20 December 2012 (UTC)

Indeed. This mistake is very common; such conditions can be phrased very conveniently in the language of category theory (using universal properties) but I won't tire you with that. It's just something that I've developed an eye for. --Lord_Farin (talk) 17:59, 20 December 2012 (UTC)

rationalisation

We have potentially a number of these formal languages in preparation in this website. There's one for a formal language used to define propositional logic (based around the work in Keisler and Robbin), and we have the formal language that is the URM, for creating the constructs that were to lead to Godel's theorem (but I ran into a brick wall). Both may well do with restructuring, but it's worth pointing out that the page structure based on the Backus-Naur form of construction used for the former may well be worth using for this as well. --prime mover (talk) 18:14, 20 December 2012 (UTC)

suggesting from the background

I will not edit this page as Timwi has worked hard on it.

I think it needs to be explained how a regular expression is an algebraic structure.

If the binary operation you are implicitly working with is concatenation then it does not work. A finite language is not closed under concatenation. --Jshflynn (talk) 18:55, 20 December 2012 (UTC)