O'Reilly logo

Express Learning: Automata Theory and Formal Languages 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

5

Context Free Grammar

5.1 CONTEXT FREE GRAMMAR: DEFINITION AND EXAMPLES

Q. Define context free grammar. Why is it called context free?

Ans. According to Chomsky Hierarchy, Context Free Grammar (CFG) is Type 2 Grammar.

In mathematical description we can describe it as

Where all the production are in the form α → β, where α images VN, i.e. set of non-terminals and /α/ = 1, i.e. there will be only one non-terminal at the left-hand-side and β images VN U Σ, i.e. β is a combination of non-terminals and terminals.

Before describing why this type of grammar is called ...

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