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.