3
$\begingroup$

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.

  • 3
    "Regular" has about a million different meanings in mathematics; it's one of the most overused words, and it's terrible.2011-05-30
  • 0
    Context restricted. Update.2011-05-30
  • 0
    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?2011-05-30
  • 1
    A similar question was asked a year ago in SO: http://stackoverflow.com/questions/975465/why-are-regular-expressions-called-regular-expressions2011-05-30
  • 1
    See also *regular* in [What are the most overloaded words in mathematics?](http://mathoverflow.net/questions/7389/what-are-the-most-overloaded-words-in-mathematics/7391#7391)2011-05-30
  • 0
    @lhf: Huge thanks! Very opulent list.2011-05-30
  • 0
    @lhf: "A similar question was asked..": and they gave no answer to my question, even such as Reghizzia and Mandriolia did.2011-05-30
  • 0
    Perhaps the answer is "regular = disciplined and obeying strong laws" because "regular sets are closed under concatenation, union and Kleene star".2011-05-30
  • 0
    There is term "regular army". Is it somewhat related?2011-05-30

2 Answers 2

2

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.

  • 0
    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".2011-05-30
  • 0
    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).2011-05-30
  • 0
    "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.2011-05-30
  • 0
    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.2011-05-30
  • 0
    "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](http://www.merriam-webster.com/dictionary/regular+), the grammar is 2, the army is 5.2011-05-31
  • 0
    Okay, I accept it, but I have some doubts anyway. Is there are any definitions of regular something in mathematics that are definitely not simple but obeying many strong laws?2011-05-31
  • 0
    And one more question: are there any definitions of things what are simple but irregular?2011-05-31
  • 0
    That's intriguing, but I am afraid that I won't find a final evidence. However, the challenge could be like this: if you bring me something simple and irregular, I will show you that the corresponding regular is simpler; if you bring me something complex and regular, I will show you that the corresponding irregular is even more complex.2011-05-31
1

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.

  • 0
    I doubt that theorists who invented regular languages/sets were somewhat related to any engineering.2011-05-30
  • 0
    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".2011-05-31