Regular Language

languages

Definition

Regular Language

A language is called regular if there exists a finite automaton that accepts it.

Equivalently: A language is called regular if all words in the language are formed by and closed under unity, concatenation or star exponent.

Formally, a set of regular languages over is the smallest set such that:

• for all

Operations

Unity

Concatenation

Exponents

Star

Plus

Closure

The class of regular languages over an alphabet is closed under the following operations:

• union, concatenation, and Kleene star by definition,
• plus, since

• complement with respect to ,
• intersection, since

• difference, since

• reversal, by reversing all transitions and exchanging start and accepting states in a suitable automaton construction,
• homomorphisms, by replacing each symbol by the word .

Observation

For complement, one first constructs a deterministic finite automaton and then swaps accepting and non-accepting states. The trap state must be included if needed so that the transition function is total.

Limitation

Regularity has limitations. Take the following language:

The language above demands that we have the number of ones is equal to the preceding number of zeros, i.e. the machine has to remember the number of zeros. Given that is not bounded, the machine has to be able to remember an unbounded number of possibilities, which is impossible with a finite number of states (in a finite automaton).

Examples

Finite complement

Every language with finite complement is regular.

Let be a language such that is finite. Then is regular, because every finite language is regular.

Regular languages are closed under complement. Hence is regular.