nLab
regular language

Contents

Contents

Idea

Regular languages are a simple kind of formal languages, the least expressive in Chomsky hierarchy.

Definition

Fix a finite vocabulary VV and denote its free monoid by V V^\star. A language LV L \subseteq V^\star is regular whenever there is a formal grammar G=(V,X,R,s)G = (V, X, R, s) that generates it (i.e. L(G)=LL(G) = L) such that all rules in RR are of the form xwxx \to w x' for a terminal wVw \in V and non-terminal symbols x,xXx, x' \in X.

Properties

Regular languages can be characterised by regular expressions:

  • the empty language \emptyset is regular,
  • every terminal symbol {wV}\{w \in V\} is regular,

if LL and LL' are regular, then:

  • their union LL={αV |αLαL}L \cup L' = \{\alpha \in V^\star \vert \alpha \in L \vee \alpha \in L' \} is regular,
  • their concatenation LL={αV |βL,γLα=βγ}LL' = \{\alpha \in V^\star \vert \exists \beta \in L, \gamma \in L' \cdot \alpha = \beta \gamma \} is regular,
  • the Kleene star L ={αV |βL,nα=β n}L^\star = \{ \alpha \in V^\star \vert \exists \beta \in L, n \in \mathbb{N} \cdot \alpha = \beta^n \} is regular.

Every regular language can be generated in that way.

A language is regular whenever it can be recognised by a finite-state automaton.

Created on November 24, 2020 at 13:28:26. See the history of this page for a list of all contributions to it.