Regular language

In theoretical computer science is a regular language is a formal language that is subject to some restrictions. Regular languages ​​can be recognized by finite automata and are described by regular expressions.

Properties

Whether a language is more or less restricted, arises from their position in the Chomsky hierarchy. The class of regular languages ​​corresponds within the Chomsky hierarchy of the most restricted class of languages ​​of type 3 It forms a proper subset of context-free languages. It has a high practical importance in computer science.

Definition

A language over an alphabet, ie a set of words is, then regular if it satisfies one of the following equivalent conditions:

  • Is generated from a regular grammar.
  • Is accepted by a finite automaton.
  • Can be represented by a regular expression.
  • The defined in relation has finite index by ( Myhill - Nerode ).
  • Can be defined in the Monadic Logic 2nd stage

Proof of the regularity of a language

If you want to prove for a given language, that it is regular, then you have to then put it on a regular grammar, a finite state machine (such as a Moore machine ) or a regular expression or lead back to already known regular languages ​​. For a proof that a language is not regular, it's usually advisable, the pumping lemma ( = Pumplemma ) to use for regular languages ​​or in more difficult cases to prove that the index of non- finite.

Examples

Be an alphabet.

  • All finite languages ​​over, that is, are regular.
  • All context-free languages ​​over a unary alphabet, that is, are regular.

Closure properties

The class of regular languages ​​is closed under the usual set operations union, intersection and complement. In addition, the isolation also applies to the so-called concatenation and Kleene star. In detail, so the following applies:

  • The union of two regular languages ​​and is regular.
  • The intersection of two regular languages ​​and is regular.
  • The complement of a regular language is regular.
  • The concatenation of two regular languages ​​and is regular.
  • The Kleene star of a regular language, that is, any frequent concatenation of words from the language associated with the empty word, is regular.

Typical decision-making problems

Be, and given regular languages ​​over the alphabet. Then the following typical problems arise:

  • Word problem: Belongs to a word?
  • Emptiness problem: Is the empty set?
  • Finiteness problem consists of a finite set of words?
  • Equivalence problem: Applies?
  • Inclusion problem: Applies?

All these problems are decidable. Up to the equivalence problem and the inclusion problem these problems even with context-free languages ​​( the next highest after the Chomsky hierarchy language class) are decidable.

Finite-state machine Myhill–Nerode theorem Closure (mathematics) Word problem (computability) Digital Object Identifier
676623
de