Skip to content
Home » Regular Languages

Regular Languages

1. Definition

A Regular Language is a language that can be recognized by a Finite Automaton, such as a DFA or NDFA.

In very simple words:

If a language can be recognized by a finite automaton, it is called a Regular Language.

Regular languages are one of the most important topics in Theory of Computation.


2. Example

Suppose:\[ \Sigma=\{0,1\} \]

Consider:\[ L=\{w\mid w\text{ ends with }1\} \]

Some strings in this language are:

  • 1
  • 01
  • 11
  • 101
  • 1001

This language is regular because we can create a DFA to recognize it.


3. How can we represent a Regular Language?

A regular language can be represented in several equivalent ways:

1. Finite Automaton

It can be recognized by:

  • DFA
  • NDFA

2. Regular Expression

For example:\[ (0+1)^*1 \]

represents strings over {0,1} ending in 1.

3. Regular Grammar

A regular language can also be generated by a Regular Grammar.

Therefore, an important relationship is:\[ \boxed{ DFA \equiv NDFA \equiv Regular\ Expression \equiv Regular\ Grammar } \]

All of them describe/recognize Regular Languages.


4. Examples of Regular Languages

Example 1

All strings over {0,1} ending in 0.\[ L=\{w\mid w\text{ ends with }0\} \]

Regular expression:\[ (0+1)^*0 \]


Example 2

All strings containing only a:\[ L=\{a,aa,aaa,aaaa,\ldots\} \]

Regular expression:\[ a^+ \]

This is regular.


Example 3

All binary strings having an even number of 0s.

This can be recognized using a DFA with two states:

  • Even number of 0s
  • Odd number of 0s

Therefore, it is a Regular Language.


5. Properties of Regular Languages

Regular languages have several important properties.

Closed under Union

If \(L_1\) and \(L_2\) are regular:\[ L_1\cup L_2 \]

is also regular.

Closed under Intersection

\[ L_1\cap L_2 \]

is also regular.

Closed under Complement

If \(L\) is regular:\[ \overline{L} \]

is also regular.

Closed under Difference

\[ L_1-L_2 \]

is also regular.

Closed under Concatenation

If \(L_1,L_2\) are regular:\[ L_1L_2 \]

is also regular.

Closed under Kleene Star

\[ L^* \]

is also regular.


6. Regular vs Non-Regular Language

Regular LanguageNon-Regular Language
Can be recognized by DFA/NDFACannot be recognized by finite automaton
Can be represented by regular expressionCannot be represented by regular expression
Can be generated by regular grammarCannot be generated by regular grammar
Has limited memory requirementsOften requires more memory
Example: \(0^*1^*\)Example: \(\{0^n1^n\mid n\geq0\}\)

Important Example

Consider:\[ L=\{0^n1^n\mid n\geq0\} \]

It contains:\[ \epsilon,\ 01,\ 0011,\ 000111,\ldots \]

This is not regular because a finite automaton cannot remember how many 0s occurred and then compare that number with the number of 1s.

This type of question is usually proved using the Pumping Lemma.


⭐ Exam Answer — 5–10 Marks

A Regular Language is a language that can be recognized by a finite automaton such as a DFA or NDFA. It can also be represented using a regular expression and generated using a regular grammar.

For example, consider:\[ L=\{w\mid w\text{ ends with }1\} \]

This language is regular because a DFA can recognize whether the last symbol of the input is 1.

Regular languages are closed under several operations such as union, intersection, complement, difference, concatenation and Kleene star.

Regular languages can be represented equivalently using:\[ \boxed{DFA \equiv NDFA \equiv Regular\ Expression \equiv Regular\ Grammar} \]

An example of a non-regular language is:\[ L=\{0^n1^n\mid n\geq0\} \]

because a finite automaton cannot remember and compare an arbitrary number of 0s and 1s.

🧠 Fast memory trick

Regular Language = DFA/NDFA can recognize it.

And remember the four:

DFA ↔ NDFA ↔ Regular Expression ↔ Regular Grammar