Talk:Regular language

From Wikipedia, the free encyclopedia

You have new messages (last change).

I removed the following:

The word regular is used because these expressions are built up using very distinct limited and regulated syntax rules.

I think one could argue that context-free languages are also built according to limited syntax rules. I'm pretty sure the word "regular" was chosen without much thinking; it's one of those meaningless terms, like "normal", that are used all over the place. Also, the above "these expressions" seems to refer to regular expressions, but regular expressions hadn't been mentioned in the article at that point. --AxelBoldt

A regular language is a formal language (i.e. a possibly infinite set of finite sequences of symbols from a finite alphabet) that has one of the following equivalent properties:

  • (...)
  • it can be described by a regular expression.

Modern "regular" expressions can describe more languages than just regular ones. Example: /([a-z]*)\\1/ (weird software problem - there should be 1 backslash there) --Taw

Obviously, this refers to regular expressions in the sense used in the theory of computation, not Perl regular expressions etc. -- Schnee 12:16, 13 Jun 2004 (UTC)

I'm reading about regular languages for the first time, so am curious about few things which I could not find in the article.

  1. Why the word 'regular' ? I can see a line on this talk page about it, but it'd be good if a line is added to the main article as well.
  2. Examples of some regular languages
  3. What do you call a language thats not a regular language. An "irregular language" ? If there is anything of the sort, a link to it and maybe an example would help understand this article better.

Jay 07:48, 14 Nov 2003 (UTC)

An example of a regular language might be that consisting of all words formed by three a's followed by any number of b's (with the alphabet consisting of a and b). I don't know where the term "regular" comes from, but I guess it's historic; as for non-regular languages, I never heard of a special moniker for them (outside of "non-regular"). -- Schnee 12:16, 13 Jun 2004 (UTC)

'# it can be accepted by a deterministic finite state machine.' is superfluous. Every NFA has an equivalent DFA. So by requiring a regular language to be accepted by an NFA requires it to be accepted by a (the corrisponding DFA)

That's not superfluous. All the properties listed are equivalent, after all, and to the uninitiated, it's not obvious that DFAs and NFAs are basically the same. -- Schnee 12:16, 13 Jun 2004 (UTC)

This article describes the properties of regular languages and gives a few examples, but I think a kind of formal definition was missing. I added a well-known recursive definition. I think it fits pretty well in the article. What do you think? --Alexandre 22:27, 25 Jun 2004 (UTC)

[edit] Kleene star

The recursive definition is quite nice. There's something I don't understand here, though. Why is the kleene star required in the recursive definition? It seems to me that you can construct it by induction using concatenation.

Here's a proof. Is it incorrect somewhere?

Suppose L is regular. If \{\epsilon\} \cup L \cup L^2 \cup \cdots \cup L^n is regular, then concatenate L to get that L \cup L^2 \cup \cdots \cup L^{n+1} is regular. Union with {ε}. Therefore L* is regular.

The trick is that ordinary induction cannot "go to infinity". Your proof only establishes that the language \{\epsilon\} \cup L \cup L^2 \cup \cdots \cup L^n is regular for all integers n. But none of these languages includes all of L*, only their union does, and regular languages are not closed under infinite unions. (if they were, every countable language would be regular) Deco 21:56, 5 December 2005 (UTC)


Can anybody talk about properties of non - regular languages?


Totally and utterly incomprehensible. Good thing no-one reads this Wikipedia rubbish except the tossers who write it.

[edit] What are half, log, and sqrt?

The article states that regular languages are closed under the "half", "log" and "sqrt" operations. What are these? I could guess that \mathrm{sqrt}(L) = \{x \in \Sigma^*|xx \in L\}, but that is not the inverse of the square of a language. I have no idea for the other two. Eric119 19:31, 14 August 2006 (UTC)

I have removed the claim, since it seems bogus to me. If these functions are real and anyone knows what they are, please add them back in (with an explanation!). Eric119 05:32, 18 August 2006 (UTC)

[edit] HALF(L)

Regular languages most definitely are closed under this operation. The proof is a little long and I am not including it here. It can be found in the text of Problem Solving in Automata, Languages, and Complexity by Ding-Zhu Du and Ker-I Ko. The basic idea however is that if L is regular, then a DFA exists that accepts it. We want to make a new machine that has this original machine and also a copy of it that runs backwards (non-deterministically). We want to run these in parallel on input. If the parallel machines stops with both machines in the same state (note that this state is not necessarily in the set of final states of the original machine) then we have half of L Isometric 05:40, 17 October 2006 (UTC)

Thanks. I was not aware of what the "half" function is, and didn't succeed in finding out. Though just now I did a Google search that found the answer. I'll add a definition to the article. Eric119 06:05, 18 October 2006 (UTC)
Incidentally, I believe I proved that the regular languages are closed under the "sqrt" operation I defined above, but it was rather tricky. Eric119 06:12, 18 October 2006 (UTC)
Retrieved from "http://en.wikipedia.org../../../r/e/g/Talk%7ERegular_language_91c3.html"