Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Why regular languages are called "regular"? Are there any mathematical (formal or not) characterization of that word per se?

The word is overused in mathematics in unsystematisable manner so we restrict context by formal languages.

share|improve this question
3  
"Regular" has about a million different meanings in mathematics; it's one of the most overused words, and it's terrible. –  Qiaochu Yuan May 30 '11 at 9:22
    
Context restricted. Update. –  Vag May 30 '11 at 9:24
    
Wonderful "Algebraic properties of structured context-free languages: old approaches and novel developments" by Stefano Crespi Reghizzia and Dino Mandriolia said: "The operators union, concatenation, and Kleene star are called regular." Anyone has something to add? –  Vag May 30 '11 at 9:25
    
A similar question was asked a year ago in SO: stackoverflow.com/questions/975465/… –  lhf May 30 '11 at 12:27
1  
See also regular in What are the most overloaded words in mathematics? –  lhf May 30 '11 at 12:30

2 Answers 2

up vote 1 down vote accepted

I think that ultimately we can translate regular with simple, that is to say, it needs fewer data to be defined. A regular pentagon is completely defined by giving just the length of one side, while a non-regular one may need up to five sides plus some angles.

As per formal languages, these are generated by grammars, and in Chomsky hierarchy, regular grammars are definitely the simplest, because terminals and non-terminals are forced to be grouped on their own side in the production rules.

share|improve this answer
    
Star-free regular languages are even simpler than RE. What means "terminals and non-terminals are forced to be grouped on their own side in the production rules"? Can you please elaborate on this a bit in the comments? And I feel that "controllable" or "well behaving" or "obeying" is more adequate translation for "regular" than "simple". –  Vag May 30 '11 at 14:35
    
With "forced to be grouped" I meant that in right-regular terminals go on the left and non-terminals go on the right (equivalent assertion for left-regular). Agreed on star-free, but it is a sub-class of regular grammars: probably the attribute "regular" requires a larger (more important) class (don't be too strict, intuition wins over rigor here). –  Halberdier May 30 '11 at 15:35
    
"I meant that in right-regular terminals go on the left and non-terminals go on the right (equivalent assertion for left-regular" It is not true. Regular grammar must have productions in the form X -> a or X -> aY so there are only one terminal and only one nonterminal, not group. –  Vag May 30 '11 at 16:29
    
I'm almost convinced but it I feel the answer must be somewhat supported by mainstream community and not be only our personal intuitions. And what about regular army? It lies in vein of my version. –  Vag May 30 '11 at 16:31
    
"only one terminal and only one non-terminal": true, for a moment I hoped it was equivalent, but with just two consecutive non-terminals, left-regularity is lost. Nevertheless, we only needed the definition to be simple, and like this is even simpler. About the regular army, maybe the meaning is slightly different: see here, the grammar is 2, the army is 5. –  Halberdier May 31 '11 at 8:02

I've never heard any reason why it is "regular", besides the fact that a regular expression is one that can be recognised by a finite state machine, which in turn is realizable as a fairly easy electrical circuit. So, my guess is that people named the kind of language that was easiest to handle and to understand "regular".

This is similar to "complex" numbers, which got their name at a time where most people were very puzzled about this new structure.

BTW: In the beginning, people construction computers were electrical engineers. I know that the data structure "stack" got its German name "Keller" = cellar because the circuit diagram looked like stairs leading downwards to the people who invented it.

share|improve this answer
    
I doubt that theorists who invented regular languages/sets were somewhat related to any engineering. –  Vag May 30 '11 at 15:03
    
And one more objection: "easiest to handle/understand" so much depends on background and skills so it may be said any thing may be "easiest" for one and "hardest" for another. Altrough there definitely is some inherent complexity in things it very hard to pin down using adjectives like "easy/understandable". –  Vag May 31 '11 at 14:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.