Regular language

A regular language is a type of formal language that satisfies the following properties:

The simplest languages to be considered are the regular languages, that is, those that can be generated from the basic languages, by applying Kleene's union, concatenation, and * operations a finite number of times.

It can be recognized by:

• a deterministic finite automaton
• a finite automaton not determinist
• a battery automaton
• an altered finite automaton
• a single-read Turing machine

It is generated by:

• a regular grammar
• a grammar of prefixes

It is described by:

• a regular expression

Regular languages over an alphabet

A regular language about an alphabet ・ ・ {displaystyle sigma } given is defined recursively as:

• Empty language ∅ ∅ {displaystyle varnothing } It's a regular language.
• The empty chain language {ε} is a regular language
• For all symbol a fit ・ ・ {displaystyle sigma } {a} is a regular language
• Yeah. A and B are regular languages then A B (union) A•B (concatenation) and A^♪ (Clausura or Star of Kleene) are regular languages
• Yeah. A is a regular language then (A) is the same regular language
• There are no more regular languages about ・ ・ {displaystyle sigma }

Every finite formal language constitutes a regular language. Other typical examples are all strings over the alphabet {a, b} containing an even number of a's or language consisting of several a's followed by several be's.

If a language is not regular it requires a machine with at least a complexity of Ω(log log n) (where n is the size of the input). In practice, most non-regular problems are solved with logarithmic complexity.

An infinite formal language can be regular or non-regular. The language L = {aⁿ, n > 0} is regular because it can be represented, for example, by the regular expression a⁺. The language L= {aⁿ bⁿ, n > 0} is a non-regular language since it is not recognized by any of the forms of representation listed above.

Closing properties

Regular languages are closed with the following operations, so if L and P are regular languages the following languages will also be regular:

• The complement ♫L♫! ! {displaystyle {bar {'L'}}} of L
• The Closure or Star of Kleene L^♪ of L
• Homomorphism φ(L) L
• The concatenation L'P of L and P
• The union L P of L and P
• Intersection L P of L and P
• The difference L P of L and P
• The reverse L^R of L

Decision problems

Given two finite deterministic automata A and B, as a consequence of the closure properties, the following problems are also decidable for any finite deterministic automata A and B, with L_A and L _B the languages that are accepted by automata respectively:

• Pertenence: Does L belong_A a L_B?
• Empty intersection: L_A L_B Empty?
• Empty language. Is it L_A Empty?
• Pertenence. Given w that belongs to Å*, this w in L_A?

Deciding when a language is regular

To situate regular languages in Chomsky's hierarchy, it should be noted that every regular language is also a context-free language, although the opposite statement is not true, for example: the language that contains the same number of 'a's and de 'b's is context-free but not regular. To prove that a language of this type is not regular, the Myhill-Nerode theorem is used, or the pumping lemma for example.

There are two purely algebraic approaches to define regular languages. Yeah. ・ ・ {displaystyle sigma } He's a finite alphabet and ・ ・ {displaystyle sigma }^♪ is a free monoid consisting of all chains on ・ ・ {displaystyle sigma }, f: ・ ・ {displaystyle sigma }^♪ → M is a symmetrical monoid where M is a finite monoid and S is a subset of M then the f set^-1(S) is regular. All regular language is presented this way.

If L is a subset of Σ*, define the equivalent relation ~ on Σ* as follows: u ~ v means

uw 한 L Yes and only if vw 한 L for everything w 한 σ*

The language L is regular if and only if the number of equivalence classes of ~ is finite; if this is the case, this number is equal to the number of states of the minimum deterministic automaton that L will recognize.

Finite languages

A special subset of regular languages is finite languages, those that only contain a finite number of words. These are obviously regular languages, and one could create regular expressions that would be the union of all the words in the language that would define the language.