Non-Regular Languages

COMP218 Lectures 2021-10-21

Non-Regular Language Example

Consider the following language:

\[L_0=\{0^n1^n\vert n\geq0\}\]

This is the language of any number of zeros followed by an equal number of ones.

To show that this is non-regular we reason by contradiction:

• Suppose we manage to construct a DFA $M$ for $L_0$ with $n$ states.
• We argue that something must be wrong with this DFA.
• In partucular $M$ must accept some strings outside $L_0$.

Consider we have this imaginary automaton:

stateDiagram-v2
state M {
direction LR
[*] --> a
a --> b:various transitions and states
b --> [*]
}

when we run it on the string $x$ where:

\[x = 0^{n+1}1^{n+1}\]

it should accept as $x\in L_0$:

• Since $M$ has $n$ states it must revisit some state in order to be finite when reading our infinite string.

  This is the pigeon hole principle as a DFA with $n$ states reading $n+1$ letters must revisit the same state twice.

• This results in a loop which would be invalid as you could read as many ones as you want without reading the same number of ones.

General Method for Showing Non-Regularity

Every language $L$ has the following property:

stateDiagram-v2
direction LR
[*] --> 1
1 --> ...:a1
... --> 2:ak
2 --> ....:a(k+1)
.... --> 3:a(n-1)
3 --> 2:an
2 --> 4:a(n+1)...am
4 --> [*]

For every sufficiently long input $z$ in $L$, there is a middle part in $z$ that, even if repeated any number of times, keeps the input inside $L$.

Pumping Lemma

Every regular language $L$ has the property of pumping lemma:

• There exists a number $n$ such that for all strings $z$ in $L$ longer than $n$, we can write $z=uvw$ where:
  1. $\vert uv\vert\leq n$
  2. $\vert v\vert\geq 1$
  3. For all $i\geq0$, the string $uv^iw$ is in $L$.

stateDiagram-v2
state Z{
	direction LR
	[*] --> 1
	1 --> 2:u
	2 --> 3:v
	3 --> 2:v
	2 --> 4:w
	4 --> [*]
}

Arguing Non-Regularity

If $L$ is regular then:

• There exists $n$ such that for all $z$ in $L$ longer than $n$, we can write $z=uvw$ where:
  1. $\vert uv\vert\leq n$
  2. $\vert v\vert\geq 1$
  3. For all $i\geq0$, the string $uv^iw$ is in $L$.

  We are proving that the pumping lemma holds as all regular languages have this property.

So to prove $L$ is not regular it is enough to show:

• For all $n$ there exists $z$ longer than $n$, such that for all ways of writing $z=uvw$ where:
  1. $\vert uv\vert\leq n$
  2. $\vert v\vert\geq 1$
  3. For all $i\geq0$, the string $uv^iw$ is not in $L$.

  This is showing that the opposite is true.