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:
101111011001
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 Language | Non-Regular Language |
|---|---|
| Can be recognized by DFA/NDFA | Cannot be recognized by finite automaton |
| Can be represented by regular expression | Cannot be represented by regular expression |
| Can be generated by regular grammar | Cannot be generated by regular grammar |
| Has limited memory requirements | Often 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 and1s.
🧠 Fast memory trick
Regular Language = DFA/NDFA can recognize it.
And remember the four:
DFA ↔ NDFA ↔ Regular Expression ↔ Regular Grammar
