Regular language

In theoretical computer science , a regular language or regular set or recognizable language is a formal language that has some restrictions. Regular languages ​​can be recognized by finite automata and described by regular expressions .

properties

Whether a language is more or less restricted depends on its position within the Chomsky hierarchy . The class of regular languages ​​corresponds to the most restricted language class of type 3 within the Chomsky hierarchy . It is a real subset of context-free languages . It is of great practical importance in computer science .

definition

A language over an alphabet , i.e. a set of words , is called regular if it fulfills one of the following equivalent conditions: ${\displaystyle L}$ ${\displaystyle \Sigma }$ ${\displaystyle L\subseteq \Sigma ^{*}}$

• ${\displaystyle L}$is generated from a regular grammar .
• ${\displaystyle L}$is accepted by a finite automaton .
• ${\displaystyle L}$can be represented by a regular expression .
• The relation defined by has finite index ( Myhill-Nerode theorem ). ${\displaystyle \Sigma ^{*}}$ ${\displaystyle (x,y)\in R_{L}:\Leftrightarrow (\forall z\in \Sigma ^{*}:(xz\in L\Leftrightarrow yz\in L))}$ ${\displaystyle R_{L}}$
• ${\displaystyle L}$can be defined in the monadic logic 2nd level .
• ${\displaystyle L}$is inductively defined as: Anchoring: with or or Induction: For regular languages: or or ${\displaystyle L=\{a\}}$ ${\displaystyle a\in \Sigma }$ ${\displaystyle L=\emptyset }$ ${\displaystyle L=\{\varepsilon \}}$ ${\displaystyle L_{1},L_{2}}$ ${\displaystyle L=L_{1}\cdot L_{2}}$ ${\displaystyle L=L_{1}\cup L_{2}}$ ${\displaystyle L=L^{*}}$

Proof of the regularity of a language

If one wants to prove for a given language that it is regular, one has to reduce it to a regular grammar, a finite automaton (e.g. a Moore automaton ) or a regular expression or to already known regular languages. To prove that a language is not regular, it is usually useful to use the pumping lemma (= pumping lemma ) for regular languages ​​or, in more difficult cases, to prove that the index of is not finite. ${\displaystyle L}$ ${\displaystyle R_{L}}$

Examples

• ${\displaystyle \left\{a^{i}b^{j}\mid i,j\in \mathbb {N} \right\}}$ is regular.
• All finite languages over any alphabet , i.e. H. those with , are regular. ${\displaystyle L}$ ${\displaystyle \Sigma }$ ${\displaystyle \left|L\right|\in \mathbb {N} }$
  • Example: ${\displaystyle \left\{a,ab\right\}}$
  • The empty set is also a regular language.
• All context-free languages over a unary alphabet, i.e. H. those with , are regular. ${\displaystyle \left|\Sigma \right|=1}$
• The Dyck languages are not regular.

Closing properties

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

• The union of two regular languages and is regular. ${\displaystyle L=L_{1}\cup L_{2}}$ ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$
• The intersection of two regular languages and is regular. ${\displaystyle L=L_{1}\cap L_{2}}$ ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$
• The complement of a regular language is regular. ${\displaystyle {\overline {L}}={\Sigma }^{*}\setminus L}$ ${\displaystyle L}$
• The concatenation of two regular languages and is regular. ${\displaystyle \{uv\mid u\in L_{1}\land v\in L_{2}\}}$ ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$
• The Kleene star of a regular language , i.e. H. the arbitrarily frequent concatenation of words from the language combined with the empty word is regular. ${\displaystyle L^{*}}$ ${\displaystyle L}$ ${\displaystyle L}$
• The difference between two regular languages and is regular. ${\displaystyle L=L_{1}\setminus L_{2}}$ ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$

Typical decision problems

Let , and given regular languages ​​above the alphabet . The following typical problems then arise: ${\displaystyle L}$ ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$ ${\displaystyle \Sigma }$

• Word problem : does a wordbelong? ${\displaystyle w\in \Sigma ^{*}}$ ${\displaystyle L}$
• Emptiness Problem : IsThe Empty Set? ${\displaystyle L}$
• Finiteness problem : consistsof a finite set of words? ${\displaystyle L}$
• Equivalence problem : is it true? ${\displaystyle L_{1}=L_{2}}$
• Inclusion problem: applies ? ${\displaystyle L_{1}\subseteq L_{2}}$

All of these problems are decidable . With the exception of the equivalence problem and the inclusion problem, the problems mentioned can also be resolved in context-free languages ​​(the next higher language class after the Chomsky hierarchy).

literature

• Michael Sipser: Introduction to the Theory of Computation . PWS Publishing, Boston et al. 1997, ISBN 0-534-94728-X , Chapter 1: Regular Languages .
• Uwe Schöning : Theoretical Computer Science - in a nutshell . 4th edition. Spectrum, Heidelberg et al. 2001, ISBN 3-8274-1099-1 , ( spectrum university paperback ), chapter 1.2: Regular languages .
• John E. Hopcroft , Rajeev Motwani, Jeffrey D. Ullman : Introduction to Automata Theory. Formal languages ​​and complexity theory . 2nd revised edition. Pearson Studium, Munich 2002, ISBN 3-8273-7020-5 , ( i - Computer Science ).
• Dag Hovland: The Inclusion Problem for Regular Expressions . In: LNCS Language and Automata Theory and Applications . tape 6031 , 2010, p. 309-320 , doi : 10.1007 / 978-3-642-13089-2_26 ( PDF ).

Web links

• REG . In: Complexity Zoo. (English)

References and comments

1. ↑ That already results from the final properties of cut and complement, there is. ${\displaystyle L_{1}\setminus L_{2}=L_{1}\cap {\overline {L_{2}}}}$