# context-free grammars

(60 minutes to learn)

## Summary

Context-free grammars are a formalism for defining the syntax of formal languages. Strings are generated by applying a sequence of productions, each of which replaces a nonterminal symbol with a sequence of terminals and nonterminals. They are widely used in the implementation of programming languages and in modeling the syntax of natural languages.

## Context

-this concept has no prerequisites-

## Goals

- Know the basic terminology: context-free grammars, substitution rules (or productions), variables, terminals, start variable, derivation, parse tree.

- Define how a context-free grammar specifies a language

- Be able to design context-free grammars to represent simple languages

- Define what it means for a CFG to be ambiguous, and give an example of an ambiguous grammar

## Core resources (read/watch one of the following)

## -Free-

→ Coursera: Automata

An introductory course on automata and the theory of computation.

## -Paid-

→ Introduction to the Theory of Computation

An undergraduate textbook on automata and the theory of computation.

Location:
Chapter 2, "Context-free languages," up through 2.1, "Context-free grammars," pages 99-109

Additional dependencies:

→ Automata Theory, Languages, and Computation

An undergraduate textbook on automata and the theory of computation.

Location:
Chapter 5, "Context-free grammars and languages," pages 171-215

## See also

-No Additional Notes-