A Non-Regular Language is a language that cannot be recognized by any Finite Automaton (DFA/NFA) and cannot be represented by a Regular Expression or Regular Grammar.
In simple words:
If a language needs unlimited memory or counting, it is usually non-regular.
1. Simple Definition
A language \(L\) is called non-regular if there is no finite automaton that can recognize all strings of \(L\).
For example:\[ L=\{0^n1^n\mid n\geq0\} \]
This language contains:\[ \epsilon,\ 01,\ 0011,\ 000111,\ 00001111,\ldots \]
Here, the number of 0s must be exactly equal to the number of 1s.
A finite automaton cannot remember an unlimited number of 0s and compare them with the number of 1s.
Therefore:\[ \boxed{L=\{0^n1^n\mid n\geq0\}\text{ is non-regular}} \]
2. Why Are Some Languages Non-Regular?
A finite automaton has only a finite number of states.
It cannot store unlimited information such as:
- Exact number of symbols
- Equal number of two different symbols
- Matching symbols
- Nested structures
- Balanced parentheses
For example:\[ \{0^n1^n\} \]
requires the machine to remember how many 0s occurred so that it can check the same number of 1s.
This requires unlimited memory, which a finite automaton does not have.
3. Examples of Non-Regular Languages
Example 1
\[ L_1=\{0^n1^n\mid n\geq0\} \]
Equal number of 0s and 1s.
Examples:
- 01 ✓
- 0011 ✓
- 000111 ✓
- 00111 ✗
Non-regular.
Example 2
\[ L_2=\{a^nb^nc^n\mid n\geq0\} \]
Equal number of a’s, b’s and c’s.
Examples:\[ abc,\quad aabbcc,\quad aaabbbccc \]
Non-regular.
Example 3
Balanced parentheses:\[ L=\{(),\ (()),\ (()()),\ldots\} \]
The number and nesting of parentheses can grow without limit.
Therefore, this language is non-regular.
4. How to Prove a Language is Non-Regular?
The most important method in your syllabus is:
Pumping Lemma
Basic procedure:
Step 1: Assume the language is regular.
Step 2: Select a suitable long string.
Step 3: Apply Pumping Lemma.\[ w=xyz \]
Step 4: Pump \(y\), usually by taking:\[ i=0 \]
or\[ i=2 \]
Step 5: Show that the resulting string is not in the language.
Step 6: Contradiction.
Step 7: Therefore, language is non-regular.
5. Example Using Pumping Lemma
Consider:\[ L=\{0^n1^n\mid n\geq0\} \]
Assume L is regular.
Let pumping length = \(p\).
Choose:\[ w=0^p1^p \]
Since the first \(p\) symbols are 0s, the pumping part \(y\) consists only of 0s.
Let:\[ y=0^k,\quad k>0 \]
Pump \(y\) zero times:\[ xy^0z=xz \]
We get:\[ 0^{p-k}1^p \]
Now the number of 0s is different from the number of 1s.
Therefore:\[ xz\notin L \]
This contradicts the Pumping Lemma.
Hence:\[ \boxed{L\text{ is non-regular}} \]
6. Regular vs Non-Regular Language
| Regular Language | Non-Regular Language |
|---|---|
| Can be recognized by DFA/NFA | Cannot be recognized by DFA/NFA |
| Can be represented by Regular Expression | Cannot be represented by Regular Expression |
| Can be generated by Regular Grammar | Cannot be generated by Regular Grammar |
| Needs only finite memory | Usually requires unlimited memory |
| Simple patterns | Counting/matching patterns |
| Example: strings ending in 1 | Example: \(0^n1^n\) |
7. Important Examples to Remember
For exam, remember these:\[ \boxed{\{0^n1^n\mid n\geq0\}} \]\[ \boxed{\{a^nb^n\mid n\geq0\}} \]\[ \boxed{\{a^nb^nc^n\mid n\geq0\}} \]\[ \boxed{\text{Balanced parentheses}} \]
These are common examples of non-regular languages.
⭐ Exam Answer — 5–10 Marks
Non-Regular Language is a language that cannot be recognized by any finite automaton such as DFA or NFA. It also cannot be represented by a regular expression or regular grammar.
Finite automata have limited memory. Therefore, they cannot handle problems requiring unlimited counting, matching or nesting.
For example:\[ L=\{0^n1^n\mid n\geq0\} \]
contains strings such as:\[ 01,\ 0011,\ 000111,\ldots \]
In this language, the number of 0s must be equal to the number of 1s. A finite automaton cannot remember an arbitrary number of 0s and compare it with the number of 1s.
The Pumping Lemma is commonly used to prove that a language is non-regular. We assume the language is regular, choose a sufficiently long string, pump a portion of the string, and show that the resulting string violates the language condition. This gives a contradiction.
Therefore, the language is non-regular.
🧠 Fast Memory Trick
Non-Regular = Finite Automaton cannot handle unlimited Counting / Matching / Nesting.
And for proof:
Assume Regular → Pump → Break → Contradiction → Non-Regular.
