## Context Free Languages, An Introduction

### Introduction

As you recall from
our definitions,
a context free language can be generated by a context free grammar.
These languages are, in fact, more complicated than regular languages,
which are generated by regular grammars.
Let's look at an example.
Consider the language 0n1n.
Since s → 0s1 | E generates this language, it is context free.
Apply the pumping lemma to show this language is not regular.
Replicating any substring
of 0n1n,
even once,
produces a word that is not in the language.
Thus there is no state machine that accepts this language.
We have entered a new realm.