Search⌘ K
AI Features
Home
Courses
Theory of Computation

Introduction to Context-free Grammars

Explore the fundamentals of context-free grammars including nonterminal and terminal symbols, rewrite rules, and leftmost derivations. Understand how formal grammars can generate sentences, and see practical implementation of these concepts through a Python program that produces random sentences based on grammar rules.

We'll cover the following...

Formal grammar

The term “grammar” conjures up memories of grammar school, where we learned the rules of our native language. A formal grammar, as we have already seen, is an attempt to codify the structure of languages in the abstract, based on research conducted in the 1950s, most notably by Noam Chomsky. A formal grammar consists of the following:

  • Nonterminal symbols (also called variables), one of which is the start symbol.
  • Terminal symbols (the “letters” of the alphabet in use, Σ\Sigma
...