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.

  • 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
    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
    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