Context Free Grammar: Definition, Examples, Rules, and Applications

If you are studying formal languages, automata theory, compiler design, or computer science, you will eventually encounter context free grammar. At first, the notation can look more complicated than it really is.

The basic idea is surprisingly simple: a context free grammar is a collection of rules that describes how valid strings in a language can be formed.

For example, a grammar can describe strings such as aa, aaaa, abab, or programming-language structures such as arithmetic expressions. Instead of listing every possible valid string individually, a grammar gives general production rules that can generate them.

In this guide, you will learn what context free grammar means, how its components work, how to construct one, what derivations and parse trees are, why ambiguity matters, and how CFGs are used in computer science.

What Is Context Free Grammar?

A context free grammar (CFG) is a formal system used to describe the structure of a formal language.

A CFG consists of production rules that replace a single nonterminal symbol with a sequence of terminals and/or nonterminals. The replacement can be made regardless of the symbols surrounding that nonterminal, which is where the term context free comes from.

A context free grammar is commonly written as:

If you want to understand the broader concept of grammar before exploring formal systems, learn more about what is grammar and how grammatical rules shape language.

G = (V, Σ, P, S)

where:

• V = a finite set of variables or nonterminal symbols
• Σ = a finite set of terminal symbols
• P = a finite set of production rules
• S = the start symbol

The grammar begins with the start symbol and repeatedly applies production rules until a string containing only terminal symbols is produced.

A Simple Example

Consider this grammar:

S → aSb
S → ε

Here:

• S is a nonterminal.
• a and b are terminals.
• S is the start symbol.
• ε represents the empty string.

Starting with S:

S
→ aSb
→ aaSbb
→ aabb

So the grammar can generate:

ε
ab
aabb
aaabbb
aaaabbbb
...

The language generated by this grammar is:

L = {aⁿbⁿ | n ≥ 0}

The important point is that the grammar does not need a separate rule for every string. A small set of rules describes an entire family of strings.

Why Is It Called “Context Free”?

The term context free refers to the form of the production rules.

A CFG generally has productions of the form:

A → α

where A is a single nonterminal and α is a sequence of terminals and nonterminals.

For example:

S → aSb

The rule can replace S without requiring a particular symbol to appear before or after it.

This differs from more restrictive grammar systems in which a production may depend on the surrounding context.

The Four Components of a Context Free Grammar

Understanding the four components of a CFG makes the mathematical notation much easier.

1. Variables or Nonterminals

Variables, also called nonterminals, represent grammatical structures that still need to be expanded.

They are often written using capital letters:

S
A
B
E
T
F

For example:

S → aSb

Here, S is a nonterminal.

A nonterminal does not normally appear in the final generated string. It acts as a placeholder during the derivation process.

2. Terminals

Terminals are the symbols that can appear in the final strings of the language.

For example:

a
b
+
*
(
)

A production such as:

S → aSb

contains terminals a and b, while S remains a nonterminal.

Once all nonterminals have been removed, the resulting sequence consists only of terminals.

3. Production Rules

Production rules specify how nonterminals can be replaced.

For example:

S → aSb
S → ε

These rules tell us that S can become either:

aSb

or:

ε

Production rules are the heart of a context free grammar because they determine which strings can be generated.

4. Start Symbol

The start symbol is the nonterminal from which every derivation begins.

It is commonly written as S.

For example:

S → aSb
S → ε

The derivation starts with:

S

The goal is to repeatedly apply rules until a terminal-only string is obtained.

How Does Context Free Grammar Work?

A CFG works by repeatedly replacing nonterminals according to its production rules.

Suppose we have:

Understanding how rules create structure is also important in broader grammar studies. Explore Grammar Flip to learn more about grammar concepts and how they work.

S → aSb
S → ε

We want to generate:

aaabbb

Start with:

S

Apply the first rule:

S → aSb

Now we have:

aSb

Apply the same rule again:

aSb → aaSbb

Apply it once more:

aaSbb → aaaSbbb

Finally, replace S with ε:

aaaSbbb → aaabbb

The derivation is complete because no nonterminals remain.

What Is a Derivation in CFG?

A derivation is the sequence of rule applications used to generate a string from the start symbol.

For example:

S
⇒ aSb
⇒ aaSbb
⇒ aabb

The symbol ⇒ is often used to represent a derivation step.

A string belongs to the language generated by a CFG if it can be derived from the grammar’s start symbol.

Leftmost Derivation

In a leftmost derivation, the leftmost nonterminal is expanded first.

Consider:

S → AB
A → a
B → b

The leftmost derivation is:

S
⇒ AB
⇒ aB
⇒ ab

The nonterminal A is expanded before B because A appears on the left.

Rightmost Derivation

In a rightmost derivation, the rightmost nonterminal is expanded first.

Using the same grammar:

S → AB
A → a
B → b

we get:

S
⇒ AB
⇒ Ab
⇒ ab

Both derivations generate the same string, but they choose nonterminals in a different order.

What Is a Parse Tree?

A parse tree, also called a derivation tree, represents the hierarchical structure of a string generated by a grammar.

Consider:

S → aSb
S → ε

For the string:

aabb

the structure can be represented conceptually as:

       S
     / | \
    a  S  b
      /|\
     a S b
       |
       ε

The leaves, read from left to right, produce:

aabb

Parse trees are especially important in programming languages because they show how a parser understands the structure of source code.

What Is an Ambiguous Context Free Grammar?

A CFG is ambiguous if at least one string in its language has more than one distinct parse tree, or equivalently, more than one leftmost derivation.

Consider this common expression grammar:

E → E + E
E → E * E
E → (E)
E → id

Now consider:

id + id * id

There are different possible interpretations:

(id + id) * id

or:

id + (id * id)

Without additional rules establishing operator precedence, the grammar permits multiple structures.

This is an example of ambiguity.

Why Does Ambiguity Matter?

Ambiguity can cause problems in programming-language parsing because a compiler needs to know exactly how an expression should be interpreted.

A grammar can often be redesigned to express precedence and associativity more clearly.

For example:

E → E + T | T
T → T * F | F
F → (E) | id

This structure gives multiplication a higher level of precedence than addition.

Thus:

id + id * id

is interpreted as:

id + (id * id)

rather than:

(id + id) * id

Context Free Grammar Example for Balanced Parentheses

CFGs are particularly useful for describing nested structures.

Consider balanced parentheses.

A simple grammar is:

S → (S)S
S → ε

This grammar can generate:

()
(())
()()
(()())

For example:

S
⇒ (S)S
⇒ (ε)S
⇒ ()S
⇒ ()(S)S
⇒ ()()S
⇒ ()()

The ability to represent nesting is one reason CFGs are useful in programming languages.

Context Free Grammar for Arithmetic Expressions

Another important example is an arithmetic expression grammar.

A grammar could be:

E → E + T | T
T → T * F | F
F → (E) | id

Here:

• E represents an expression.
• T represents a term.
• F represents a factor.
• + and * are terminals.
• id represents an identifier.

This grammar can generate expressions such as:

id
id + id
id * id
id + id * id
(id + id) * id

The hierarchy of E, T, and F helps encode operator precedence.

Context Free Grammar vs Regular Grammar

A regular grammar is less powerful than a context free grammar.

The main difference is the type of patterns each grammar can describe.

Feature	Regular Grammar	Context Free Grammar
Formal language class	Regular languages	Context-free languages
Recognizing machine	Finite automaton	Pushdown automaton
Handles nesting	Generally no	Yes
Handles balanced parentheses	No	Yes
Typical use	Simple patterns	Nested structures and syntax
Relative power	Less expressive	More expressive

For example, the language:

{aⁿbⁿ | n ≥ 0}

is context-free but not regular.

A finite automaton cannot keep an arbitrary count of the number of a symbols and compare it with the number of b symbols. A pushdown automaton, however, can use its stack to handle this type of dependency.

Context Free Grammar vs Context Sensitive Grammar

Context free grammars are part of the Chomsky hierarchy.

The hierarchy is commonly presented as:

1. Regular grammars
2. Context free grammars
3. Context sensitive grammars
4. Unrestricted grammars

Each level generally provides greater expressive power than the level below it.

A context free grammar has productions where a single nonterminal can be replaced independently of its surrounding symbols.

A context sensitive grammar can express some relationships that cannot be represented by a CFG.

For example, the language:

{aⁿbⁿcⁿ | n ≥ 0}

is not context-free, although it is context-sensitive.

This illustrates an important limitation: not every formal language can be described by a context free grammar.

What Is a Context-Free Language?

A context-free language (CFL) is a language that can be generated by at least one context free grammar.

In other words:

If a CFG can generate every string in a language and no invalid strings, that language is context-free.

For example:

L = {aⁿbⁿ | n ≥ 0}

is a context-free language because the grammar:

S → aSb | ε

generates it.

The terms are related but not identical:

• CFG = the system of production rules.
• CFL = the language generated by that grammar.

What Is Chomsky Normal Form?

Chomsky Normal Form (CNF) is a standardized form for context free grammars.

In a typical CNF grammar, productions have forms such as:

A → BC

or:

A → a

where A, B, and C are nonterminals and a is a terminal.

An exception is commonly allowed for the start symbol when the language contains the empty string:

S → ε

CNF is useful because it gives CFGs a predictable structure. It is also important in parsing algorithms such as the CYK algorithm.

Why Use Chomsky Normal Form?

Converting a grammar to CNF can make certain theoretical and computational procedures easier.

It is especially useful when studying:

• CFG parsing
• Formal language theory
• The CYK parsing algorithm
• Proofs about context-free languages
• Grammar transformations

What Is Greibach Normal Form?

Another standard form is Greibach Normal Form (GNF).

In a grammar in GNF, productions generally begin with a terminal followed by zero or more nonterminals.

A typical production looks like:

A → aα

where a is a terminal and α is a sequence of nonterminals.

GNF is useful in formal-language theory and can simplify certain theoretical analyses of CFGs.

How to Construct a Context Free Grammar

Creating a CFG becomes much easier when you work systematically.

Step 1: Understand the Language

First, determine exactly which strings should belong to the language.

For example:

L = {aⁿbⁿ | n ≥ 0}

The important condition is that the number of as must equal the number of bs, with all as appearing before the bs.

Step 2: Identify the Basic Structure

The desired strings look like:

ε
ab
aabb
aaabbb
aaaabbbb

Notice the pattern:

• Add one a.
• Add one b.
• Repeat as needed.

Step 3: Create a Nonterminal

Use a start symbol:

S

Step 4: Write the Recursive Rule

To add one a and one b around the existing structure:

S → aSb

Step 5: Add a Base Case

We need the recursion to stop:

S → ε

The final grammar is:

S → aSb | ε

This is a complete CFG for the language.

Common Context Free Grammar Mistakes

Learning CFGs is much easier when you know which mistakes to watch for.

Mistake 1: Confusing Terminals and Nonterminals

Consider:

S → aSb

Here, S is a nonterminal, while a and b are terminals.

A common beginner error is treating every symbol as the same type.

Tip: Decide your terminal and nonterminal sets before writing production rules.

Mistake 2: Forgetting the Base Case

Consider:

S → aSb

This rule keeps producing another S.

It can generate:

ab
aabb
aaabbb

only if there is some way to eliminate S.

Adding:

S → ε

provides the stopping point.

Mistake 3: Generating Invalid Strings

A grammar should generate only strings belonging to the target language.

If your intended language requires equal numbers of as and bs, a rule such as:

S → aS

could introduce extra as without adding corresponding bs.

Always test the grammar with several short strings.

Mistake 4: Ignoring Ambiguity

A grammar may generate the correct set of strings but still have multiple parse trees for some strings.

This is particularly important for programming-language grammars.

If structural interpretation matters, check whether the grammar is ambiguous.

Mistake 5: Assuming Every Language Is Context-Free

Not every formal language can be described by a CFG.

For example:

{aⁿbⁿcⁿ | n ≥ 0}

is not a context-free language.

Recognizing the limits of CFGs is just as important as knowing how to construct them.

Practical Tips for Solving CFG Problems

If you are preparing for an exam or learning formal language theory, the following approach can help.

Start With Small Examples

Before trying to construct a general grammar, write several valid strings:

ε
ab
aabb
aaabbb

Then identify the pattern connecting them.

Look for Recursion

Many CFGs use recursion to represent repeated or nested structures.

For example:

S → aSb

adds matching symbols around another S.

For nested structures:

S → (S)S

allows parentheses to contain other balanced structures.

Always Test Invalid Strings

Do not test only strings you want the grammar to generate.

Also test strings that should be rejected.

For:

S → aSb | ε

these should be generated:

ab
aabb
aaabbb

while these should not:

aab
abb
abab

Testing both sides helps reveal incorrect production rules.

Applications of Context Free Grammar

Context free grammars are not merely theoretical objects. They have important applications across computer science.

Compiler Design

Compilers use grammars to describe the syntax of programming languages.

A programming language may have rules describing:

• expressions
• statements
• function definitions
• blocks
• declarations
• operators
• parentheses

A parser uses these rules to determine whether source code follows the language’s syntax.

Programming Languages

Many programming-language constructs have a naturally hierarchical structure.

For example:

if (condition) {
    statement;
}

The nesting of expressions, statements, and blocks is well suited to grammar-based descriptions.

Natural Language Processing

CFGs can also model aspects of natural language syntax.

For example, a simplified grammar might include rules such as:

Understanding how sentences are structured and ideas are organized can also help with clear communication. Learn more about expository writing and how to present information in a logical, easy-to-follow way.

S → NP VP
NP → Det N
VP → V NP

where:

• S = sentence
• NP = noun phrase
• VP = verb phrase
• Det = determiner
• N = noun
• V = verb

Real human language is considerably more complicated than such a small grammar, but CFGs provide an important foundation for syntactic analysis.

Parsing

A parser takes an input string and determines whether it can be generated by a grammar.

If it can, the parser may also construct a parse tree showing its structure.

Different parsing techniques are designed for different grammar forms, including:

• LL parsing
• LR parsing
• CYK parsing
• Earley parsing

Advantages of Context Free Grammar

CFGs are popular because they provide a useful balance between simplicity and expressive power.

They Represent Hierarchical Structure

CFGs naturally describe nested structures such as:

((a))

or programming-language blocks and expressions.

They Are More Powerful Than Regular Grammars

CFGs can describe languages that finite automata cannot recognize.

For example:

{aⁿbⁿ | n ≥ 0}

is context-free but not regular.

They Are Mathematically Well Defined

CFGs provide precise rules for defining formal languages, making them useful for theoretical computer science.

They Support Parsing

There are well-established algorithms for determining whether strings belong to context-free languages and for constructing parse structures.

Limitations of Context Free Grammar

CFGs also have important limitations.

Some Languages Are Not Context-Free

A classic example is:

{aⁿbⁿcⁿ | n ≥ 0}

A CFG cannot describe this language.

Ambiguity Can Be Difficult

A grammar may generate a string in multiple ways. This can make parsing and interpretation more complicated.

Real Languages Can Be More Complex

Natural languages and modern programming languages may contain relationships that are difficult or impossible to capture cleanly using a basic CFG alone.

Additional mechanisms may therefore be required.

A Quick Context Free Grammar Cheat Sheet

Concept	Meaning
CFG	Context free grammar
G = (V, Σ, P, S)	Standard CFG representation
V	Set of nonterminals
Σ	Set of terminals
P	Production rules
S	Start symbol
ε	Empty string
Derivation	Sequence of rule applications
Parse tree	Tree showing grammatical structure
CFL	Language generated by a CFG
Ambiguous grammar	Grammar with a string having multiple parse trees
CNF	Chomsky Normal Form
GNF	Greibach Normal Form

How to Know Whether a Grammar Is Correct

When you create a context free grammar, ask four questions:

1. Does it generate every valid string?
2. Does it avoid generating invalid strings?
3. Does the recursion eventually stop?
4. Does the structure of each generated string match the intended language?

For example, for:

L = {aⁿbⁿ | n ≥ 0}

the grammar:

S → aSb | ε

works because every recursive step adds exactly one a and one b.

The order also remains correct: all as appear before the corresponding bs.

Frequently Asked Questions About Context Free Grammar

What is context free grammar in simple words?

A context free grammar is a set of rules used to generate strings in a formal language. It starts with a start symbol and repeatedly replaces nonterminals according to production rules until only terminal symbols remain.

What are the four parts of a CFG?

The four parts are:

G = (V, Σ, P, S)

V is the set of nonterminals, Σ is the set of terminals, P is the set of production rules, and S is the start symbol.

What is an example of a context free grammar?

A simple example is:

S → aSb | ε

It generates the language:

{aⁿbⁿ | n ≥ 0}

including strings such as ab, aabb, and aaabbb.

What is the difference between CFG and regular grammar?

A regular grammar has less expressive power and is associated with finite automata. A CFG is more powerful and can represent structures involving recursion and nesting, such as balanced parentheses.

What is a context-free language?

A context-free language is any language that can be generated by at least one context free grammar.

Can a CFG be ambiguous?

Yes. A CFG is ambiguous if at least one string has more than one distinct parse tree or more than one leftmost derivation.

Why are CFGs important in compiler design?

CFGs provide a formal way to describe programming-language syntax. Parsers can use those grammar rules to analyze source code and build its structural representation.

Is every language context-free?

No. Some formal languages are not context-free. For example, the language {aⁿbⁿcⁿ | n ≥ 0} is not context-free.

Conclusion

A context free grammar provides a systematic way to describe how strings in a formal language are constructed. Its four fundamental components—nonterminals, terminals, production rules, and a start symbol—work together to generate potentially infinite languages from a finite set of rules.

The key concepts to remember are derivations, parse trees, recursion, ambiguity, context-free languages, and grammar normal forms. CFGs are especially valuable when a language contains hierarchical or nested structures, which is why they play an important role in parsing, compiler design, programming languages, and aspects of natural language processing.

If you are learning CFGs for an exam, start with simple grammars, trace their derivations by hand, draw parse trees, and test both valid and invalid strings. Once those basics become comfortable, more advanced topics such as ambiguity, Chomsky Normal Form, pushdown automata, and parsing algorithms become much easier to understand.