This class will cover non regular languages, and context free grammars.
Non Regular Languages
Recall the Pigeonhole Principle:
- pigeonholes pigeons
- at least one pigeonhole with no pigeon
And the term Vacuously True:
- true because there are no elements in
And Superscripts:
These are all important because they help us to understand the concept of Non Regular Languages.
Non regular languages are languages that cannot be described by a regular expression. This is because regular expressions are limited in their ability to describe languages that have a “memory” or “state”.