Non-Regular Language

A non-regular language, as the name implies, is a language that is not a regular language. That is, there is no finite state automata (deterministic or otherwise) that can recognise it.

To prove that some language $L$ is not regular, we need to show that there is no FSA that can recognise it. This is pretty difficult, so both methods of proving non-regularity require additional tools

Proving Non-Regularity Via Pumping Lemma §

#todo

Proving Non-Regularity Via Fooling Sets §

See an example of an infinite fooling set:

Fooling Set.md

Thus, the language:

$$L=\{0^n{1}^n\}\text{ is non-regular}$$

Extending With Closure Properties §

Union §

We can use the contrapositive of some closure properties:

If we have two languages $A$ and $B$, and $A$ is regular, then if we know that $A\cup B$ is non-regular, then it must be that $B$ is non-regular.

Complement §

A much simpler one is the complement of a regular language:

Taking the contrapositive yields:

$$L^C\text{ is non-regular}⟹\text{L is non-regular}$$

Concatenation §

Regular Language.md

Again, the contrapositive means that if $A\circ B$ is not regular, then one of $A$ or $B$ (or both) are non-regular.

If we have a regular language $A$, and we somehow know concatenating it with another language $B$ to get $A\circ B$ is not regular, then the contrapositive allows us to deduce that $B$ must be non-regular.

Kleene Star §

Another easy unary operator: Regular Language.md

The contrapositive yields:

$$L^{\ast }\text{ is non-regular}⟹\text{L is non-regular}$$