O'Reilly logo

Introduction to Automata Theory, Formal Languages and Computation by Shyamalendu Kandar

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

6

Context-free Grammar

Introduction

Context-free grammar, in short CFG, is type 2 grammar according to the Chomsky hierarchy. The language generated by the CFG is called context-free language (CFL). In the previous chapters, we have discussed about finite automata and regular expression which are related to regular grammar. Regular grammar is a subset of CFG. In this chapter, we shall learn about CFG, how to derive a language from a CFG, simplification of CFG, transformation of CFG into normal form, and the pumping lemma for CFG.

6.1  Definition of Context-free Grammar

According to the Chomsky hierarchy, context-free grammar, or in short CFG, is type 2 grammar.

In mathematical description, we can describe it as

Where all the production are in ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required