Regular language . In Linguistics , Mathematics and Informatics and in the Chomsky hierarchy it refers to type 3 languages, those that can be represented by regular grammars , finite automata or regular expressions .
They are the simplest formal languages , with the most studied representation and recognition mechanisms. Its practical application in the theory and construction of interpreters and compilers of programming languages or information specification or format , especially as microcomponents of the lexicographic analyzer that detects tokens as numeric constants , text strings , operators, reserved words ( keywords ), spacers, etc. But you can also appreciate its use in vending machines ,public telephones , calculators and other electromechanical devices.
Summary
[ hide ]
- 1
- 2 Example 1.
- 3 Importance of regular languages.
- 1 Example 2
- 4 See also.
- 5 Sources
Definitions.
A language is said to be regular if and only if any of the following propositions is fulfilled:
- It has at least a regular G grammarthat produces it.
- It can be recognized by a finite automaton A.
- There is a regular expression E rrepresenting all chains L .
Within the Chomsky Hierarchy it refers to type 3 languages, the most restricted subset of formal languages within the hierarchy, as seen in the image.
A recursive-constructive definition of regular languages can also be made through the algebra of formal languages .
A regular language about an alphabet T or L R (T) is:
- The empty language {}.
- The language made up of the empty string or trivial language.
- A language {x}consisting of a single symbol x of T .
- If Aand B are regular languages over T , then AB ( Concatenation of languages ), ( Union languages ), A * ( Clausura language or Kleene star ) are also regular languages over T .
- Any other language that can be obtained from 1 to 4.
Example 1.
Show that the language made up of PROLOG variable names is a regular language.
It must first be remembered that a PROLOG variable name is given by the form:
Any word that begins with a capital letter whether or not followed by combinations of letters, digits, or underscores, or which begins with at least one underscore, whether or not followed by any sequence of alphanumeric or underlines .
Each of the following constructions are equivalent by virtue of the definition given above:
- The regular expression (A | B | … | Z) | _ (A | B | … | Z | a | b | … | z | _) *.
- The following finite automaton represented as a state diagramallows the recognition of PROLOG variables.
- A grammar with productions of the form:
- .
- .
Importance of regular languages.
The existence and formalization of regular languages (LR) and their link with other linguistic-mathematical artifacts already well formalized, studied and even put into practice has been of vital importance in the further development of the mechanisms for processing computer languages, mainly in the lexicographic analyzers thanks to the possibility of deriving the recognition of the LR by means of finite automata that are easy to implement computationally with simple and fast mechanisms, optimal in obtaining fast and robust parsers that in turn offer developers information Detailed lexical, syntactic errors and even warn about semantic errors.
The same is true for example with regular expressions already implemented in many modern general-purpose programming languages that allow language developers highly efficient mechanisms for intuitively obtaining compiler parts that recognize tokens or lexical particles in the source code as phase. of the complete process of interpretation or compilation, as the case may be.
As an illustration in the case of the previous example, we see the following Python function that, from any of the formalizing elements of the corresponding LR, allows us to decide if a text w is a PROLOG variable:
def variablePROLOG (w): ” ‘(str) -> bool. True if “w” is a correct variable name ” ‘ if (w [0] .isalpha and w [0] == w [0] .upper ()) or w [0] == ‘_’: #The first character is a capital letter or an underline w = w [1:] #The first character is removed while w and (w [0] .isalnum () or w [0] == ‘_’): # As long as there are characters in “w” and the first current character is an alphanumeric or an underline, everything is fine w = w [1:] #Remove the first character if w == ”: #If there are no elements to review, it is a PROLOG variable return true return False
Several functions of this nature compose lexicographic analyzers to discriminate the function of each token of the language in question: numerical constant, text string literal, identifier, separator, etc .; according to the case.
And it can also be seen that there is a close relationship in how to implement the LR recognition functions and the regular expression or grammar or the corresponding finite automaton, to the point that for more than 3 decades there have been lexicographic analyzer generating applications such as the Flex or the Bison .
But the scope of LRs does not stop in the world of computer language compilation as seen in the following example.
Example 2
In a Miami aquarium the intellectual capacities of the dolphins in captivity are trained and the results of one of the specimens who have learned to recognize even numbers from fish images, are particularly important, distinguishing when there is an even number or not of fish in the picture. Show that pictures of even fish numbers is a regular language that the dolphin can perceive.
Each fish in the images is defined with the lowercase letter p and it is seen that for the even images the following productions of a regular grammar can be defined:

