Talk:Regular language

From Wikipedia, the free encyclopedia

Philosophy Portal

This article is within the scope of the WikiProject Philosophy, which collaborates on articles related to philosophy. To participate, you can edit this article or visit the project page for more details.

???

This article has not yet received a rating on the quality scale.

???

This article has not yet received an importance rating on the importance scale.

Additional information:

Related task forces (core areas):
	Logic

1 The word regular
2 Regular expressions
3 Examples and other questions
4 NFA's
5 Formal definition
6 Kleene star
7 Properties of non-regular languages
8 What are half, log, and sqrt?
9 HALF(L)
10 More Than One Definition?

[edit] The word regular

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

[edit] Regular expressions

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)

[edit] Examples and other questions

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

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.
Examples of some regular languages
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)

[edit] NFA's

'# 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)

[edit] Formal definition

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)

[edit] Properties of non-regular languages

Can anybody talk about properties of non - regular languages? (unsigned, undated)

it would be of great help if some one could post more info about non regular languages 7 OCT 2007 —Preceding unsigned comment added by 64.234.33.191 (talk) 19:18, 7 October 2007 (UTC)

[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)

I don't have a definition, but I think I have some examples (just guessing)-- for example, if

L = a * b *

(i.e.

L = Σ *

for

Σ = {a, b}

) then half(L) would be the set of strings starting only with the letter b. The other half would be the strings starting only with the letter a. The two halves add to the whole language. The square-root would be

s q r t (L) = (a b) * = a * = b *

-- i.e. just take half number of the generators. Finally, log just extracts the generators from out of the language, so if

L = a *

then

l o g (L) = {a}

. Or something like that. I don't know the general definition. linas 04:00, 26 April 2007 (UTC)

The statement is true. http://www.cs.caltech.edu/~cs20/a/hw/hw2/solution/sol2.pdf (i hope i am not infringing anything by posting this link)

Not at all. And in the homework assignment corresponding to those solutions [1] is the definition of these sets:

Half(L) = { x | ∃ y ( |y| = |x| and xy ∈ L)}

Sqrt(L) = { x | ∃ y ( |y| = |x|² and xy ∈ L)}

Half(L) = { x | ∃ y ( |y| = 2^|x| and xy ∈ L)}

What is not clear to me is that these are significant at all, other than as a homework problem. — Carl (CBM · talk) 18:10, 11 September 2007 (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)

I removed the statement

* HALF(L), the set of strings that are the first half of a string in L

from the article, as its (clearly?) wrong. A standard textbook example of a language that is not regular is $\{a^nb^n\vert n\ge 0\}$ . I'll try to supply a proof that its not regular shortly. linas 03:47, 26 April 2007 (UTC)

Isometric is talking about something completely different; he is not talking about "half of a string", he is talking about "half of a language", which has "half" as many strings in it as the original language does. Similarly for the definition sqrt(L), and log(L). I can kinda guess what these are, but this claim would need to be backed up by a longer article defining them so that we don't get mistakes like this. linas 03:55, 26 April 2007 (UTC)

Linas, I don't get the point of your example. That is a non-regular langauge whose "half" a* is regular. Here I am defining half as it said in the article which more explicitly is half(L) = {x | exists y length(x) = length(y) and xy in L}. Incidentally, the document at http://www.comp.nus.edu.sg/~sanjay/cs3231/half.pdf claims a proof of closure, but I haven't verified it myself. Eric119 20:15, 28 April 2007 (UTC)

[edit] More Than One Definition?

The Article first describes regular language as one that is accepted by a deterministic finite state machine. Then it defines it using the recursive definition. The point is that either one can be used as definition. However, if one is used as definition, the other one must be proved as theorem.--CBKAtTopsails 16:20, 6 June 2007 (UTC)

This is implied by the word "equivalent", but may deserve clarification. Dcoetzee 18:15, 11 September 2007 (UTC)