nLab
regular language

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:

if LL and LL' are regular, then:

Every regular language can be generated in that way.

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