An Introduction to Formal Languages and Automata, 7th Edition

5.1 CONTEXT-FREE GRAMMARS

The productions in a regular grammar are restricted in two ways: The left side must be a single variable, while the right side has a special form. To create grammars that are more powerful, we must relax some of these restrictions. By retaining the restriction on the left side, but permitting anything on the right, we get context-free grammars.

DEFINITION 5.1

A grammar G = (V, T, S, P) is said to be context-free if all productions in P have the form

$$A\to x,$$

where A ∈ V and x ∈ (V ∪ T)^*.

A language L is said to be context-free if and only if there is a context-free grammar G such that L = L(G).

Every regular grammar is context-free, so a regular language is also a context-free one. But, as we know from simple examples ...