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 0ⁿ1ⁿ. 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 0ⁿ1ⁿ, 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.