Regular language

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Intheoretical computer science, aregular languageis aformal language(i.e., a possibly infinite set of finite sequences of symbols from a finite alphabet) that satisfies the following equivalent properties:

  • it can be accepted by adeterministic finite state machine
  • it can be accepted by anondeterministic finite state machine
  • it can be accepted by anondeterministic finite state machine
  • it can be accepted by analternating finite automaton
  • it can be described by a formalregular expression. Note that the "regular expression" features provided with many programming languages are augmented with features that make them capable of recognizing languages which are not regular, and are therefore not strictly equivalent to formal regular expressions.
  • it can be generated by aregular grammar
  • it can be generated by aprefix grammar
  • it can be accepted by a read-onlyTuring machine
  • it can be defined inmonadicsecond-order logic
  • it is recognized by some finitely generatedmonoid
  • it is the preimage of a subset of a finite monoid under a homomorphism from the free monoid on its alphabet

The collection of regular languages over an alphabet S is defined recursively as follows:

  • the empty language Ø is a regular language.
  • theempty stringlanguage { e } is a regular language.
  • For eacha? S (abelongs to S ), thesingletonlanguage {a} is a regular language.
  • IfAandBare regular languages, thenA?B(union),A•B(concatenation),A* (Kleene star) andB* are regular languages.
  • No other languages over S are regular.

All finite languages are regular. Other typical examples include the language consisting of all strings over the alphabet {a,b} which contain an even number ofas, or the language consisting of all strings of the form: severalas followed by severalbs.


To locate the regular languages in theChomsky hierarchy, one notices that every regular language iscontext-free. The converse is not true: for example the language consisting of all strings having the same number ofa's asb's is context-free but not regular. To prove that a language such as this is not regular, one uses theMyhill-Nerode theoremor thepumping lemma.

There are two purely algebraic approaches to define regular languages. If S is a finite alphabet and S* denotes thefree monoidover S consisting of all strings over S, f: S* ?Mis amonoid homomorphismwhereMis afinitemonoid, andSis a subset ofM, then the setf-1(S) is regular. Every regular language arises in this fashion.

IfLis any subset of S*, one defines anequivalence relation~ (called thesyntactic relation) on S* as follows:u~vis defined to mean

uw?Lif and only ifvw?Lfor allw? S*

The languageLis regular if and only if the number of equivalence classes of ~ is finite (A proof of this is provided in the article on thesyntactic monoid). When a language is regular, then the number of equivalence classes is equal to the number of states of theminimal deterministic finite automatonacceptingL.

A similar set of statements can be formulated for a monoidM\subset\Sigma^*. In this case, equivalence overMleads to the concept of arecognizable language.


The regular languages areclosedunder the various operations. Below,KandLrepresent regular languages.

  • The set theoretic Boolean operations:union ,intersectionK , andcomplement bar{L}. From this alsodifference follows.
  • The regular operations:unionK ,concatenation , andKleene starL*.
  • Thetriooperations:string homomorphism, inverse string homomorphism, and intersection with regular languages. As a consequence they are closed under arbitraryfinite state transductions, likequotientK/Lwith a regular language.
  • The reverse (or mirror image)LR.
Regular Language consists of:

Regular expression- Incomputing,regular expressions, also referred to asregexorregexp, provide a concise and flexible means for matchingstringsof text, such as particular characters, words, or patterns of characters. A regular expression is written in aformal languagethat can be interpreted by a regular expression processor, a program that either serves as aparser generatoror examines text and identifies parts that match the providedspecification.

The following examples illustrate a few specifications that could be expressed in a regular expression:

  • The sequence of characters "car" in any context, such as "car", "cartoon", or "bicarbonate"
  • The word "car" when it appears as an isolated word
  • The word "car" when preceded by the word "blue" or "red"
  • A dollar sign immediately followed by one or more digits, and then optionally a period and exactly two more digits

Finite automata- Automata theoryis the study ofabstract machinesand the problems which they are able to solve. These abstract machines are called automata. A discrete automaton is a mathematical model for afinite state machine(FSM). An FSM is a machine that takes a symbol as input and "jumps" ortransitions, from one state to another according to atransition function(which can be expressed as a table). For example in "Mealy" variety of FSMs, this transition function tells the automaton which state to go to next given a current state and a current symbol.


Although regular model checking is a powerful technique, there are several classes of parameterized systems whose behaviors cannot be captured using regular languages. The paper considers symbolic model checking using classes of languages more expressive than the regular languages and provides model checking of non-regular parameterized systems (using classes of context-free languages)

Moreover, in many cases, the processes in a parametrized network are infinite-state because of unbounded or parametrized data structures.

How can we prove whether or not a language is regular?

Theorem: Pumping Lemma

If A is a regular language, then there is a number p where, if s is any string in A of length at least p, then s may be divided into 3 pieces s = xyz, satisfying:

  1. for each i _ 0, xyiz 2 A,
  2. |y| > 0, and
  3. |xy| _ p.

p is called the pumping length.

Example-Show that A = {0n1n | n _ 0} is non-regular

Assume that A is regular. Let p be the pumping length. Now consider the string s = 0p1p which is in A.

From the Pumping lemma, we can write s = xyz so that any xyiz is also in A for i _ 0. There are 3 cases for y:

  1. y = 0t: repeating y will give us more 0s than 1s. So xyyz is not in A.
  2. y = 1t: repeating y will give us more 1s than 0s. So xyyz is not in A.
  3. y = 0t1s: clearly xyyz = 00 · · · 011 · · · 100 · · · 011 · · · 1 is not in A.

This contradicts our assumption that A is regular.