Course contentsShow
← Computer Science
Lesson 1813 of 2,87241. Context-Free LanguagesFree lesson

Context-Free Grammars: Definition and Components

Learn the formal definition of CFGs including terminals, nonterminals, start symbol, and production rules.

Context-Free Grammars: Definition and Components

What you'll learn: You'll understand the four essential parts that make up a context-free grammar and how they work together to define a language.

Why Context-Free Grammars?

While regular expressions and finite automata are powerful, they can't describe all the patterns we need in computer science—like balanced parentheses or nested structures. Context-free grammars (CFGs) step up to handle these more complex languages.

The Four Components

A context-free grammar is formally defined by four elements:

1. Terminals (Σ)

These are the actual symbols that appear in strings of the language—like letters, digits, or punctuation. They're called "terminals" because they can't be broken down further. Think of them as the "leaves" of a tree.

2. Nonterminals (V)

These are placeholder variables that represent patterns or structures. Written in uppercase (like A, B, S), they get replaced during the generation process. They're like recipe ingredients that need further preparation.

3. Start Symbol (S)

One special nonterminal where every derivation begins. It's the "root" from which all valid strings grow.

4. Production Rules (P)

These are the grammar's instructions, written as A → α, where A is a nonterminal and α is any string of terminals and/or nonterminals. Each rule says "you can replace this nonterminal with that pattern."

How They Work Together

Think of a CFG as a recipe book: the start symbol tells you where to begin, nonterminals are intermediate steps, production rules are the instructions, and terminals are the final ingredients in your dish.

For example, a grammar for balanced parentheses might have: start symbol S, terminals ( and ), and rules like S → (S) and S → ε (empty string).

Key Takeaway: A context-free grammar consists of four components—terminals, nonterminals, a start symbol, and production rules—that together define how to generate all strings in a context-free language.