Can a CFG contain an empty expansion?

Yes. Formal definitions can allow the empty string on a rule's right side, although a particular grammar or normal form may restrict such rules.

Is a probabilistic CFG different?

It adds probabilities to productions, enabling scores for derivations under specified assumptions.

Does context-free grammar mean Constraint Grammar?

No. The names refer to different formalisms; the similar abbreviations should not be treated as interchangeable.

AI Glossary / Natural language and speech / Intermediate

Context-free grammar

Definition

A context-free grammar, or CFG, is a formal system of rules for building strings and describing their hierarchical structure. Each rule replaces one nonterminal symbol with a sequence of symbols, without requiring a particular surrounding sequence for that replacement.

What it means

A nonterminal is a label for something that can be expanded, such as a sentence or noun phrase. Terminals are the final symbols, often words in a language example. A designated start symbol tells us where a complete derivation begins.

Context-free describes the form of the rules. It does not mean that human communication has no context, that the grammar understands a conversation, or that its output is factually correct. A rule for expanding a noun phrase can be used wherever that nonterminal appears in a derivation.

CFGs are useful for explaining nested structure, building parsers and defining parts of formal languages. A particular grammar covers only what its rules allow. It may be a tiny teaching language rather than an adequate model of all English sentences.

How it works

The grammar specifies terminals, nonterminals, production rules and a start symbol. A rule such as S → NP VP says that the symbol S can expand into a noun phrase followed by a verb phrase. Further rules eventually replace these labels with terminal words.

Generation asks which strings can be produced from the start symbol. Parsing works from an observed string and asks which structures, if any, the grammar licenses. The grammar supplies the possible structures; a parsing algorithm searches or organizes them. These are different components.

Recursion allows a rule to include a symbol that can eventually lead back to itself, supporting repeated or nested structures. Ambiguity occurs when a string has more than one parse tree under the grammar. A plain CFG need not choose a preferred tree. Probabilities or other scores can be added, but they are additional modeling choices, not an automatic consequence of the rule format.

Three practical examples

A language class uses a small grammar to show how a noun phrase and a verb phrase form a sentence.
A software team specifies the allowed nesting of a structured command language before writing its parser.
A text-analysis project uses constituency parsing to identify candidate phrase boundaries, then evaluates whether the chosen structures fit its documents.

Think of it this way

Think of assembly instructions containing named subassemblies. A cabinet instruction can call for a drawer, and the drawer instruction explains its own components wherever that drawer is requested.

This resembles replacing a nonterminal using its production rule. The analogy does not imply that every assembled sentence is sensible or that ordinary language follows one complete instruction book. Physical compatibility constraints also need their own representation; they are not magically supplied by naming a subassembly.

Worked example

Deriving a small sentence

Use this deliberately limited grammar: S → NP VP; NP → Det N; VP → V NP; Det → the; N → analyst | report; V → reviewed. The vertical bar means an alternative, so the noun rule permits either terminal.

One derivation is S ⇒ NP VP ⇒ Det N VP ⇒ the N VP ⇒ the analyst VP ⇒ the analyst V NP ⇒ the analyst reviewed NP ⇒ the analyst reviewed Det N ⇒ the analyst reviewed the N ⇒ the analyst reviewed the report.

The resulting sentence contains five words. Its subject NP is “the analyst,” while its object NP is “the report.” The grammar also permits “the report reviewed the analyst,” because both nouns share the same category. This exposes a semantic limitation, not an error in following the listed rules. Restricting meaningful combinations would require additional modeling or a more carefully designed grammar.

Illustrative case study

A fictional office-tool team offers a small text interface for requesting reports. It begins by describing the accepted command shapes with grammar rules. Testers then submit a phrase that has two possible attachments, producing two valid structural interpretations.

The team distinguishes three questions: whether the text fits the grammar, which parse the user intends, and whether the requested operation is permitted. It adds a clarification step for the ambiguous form and checks permissions separately before executing anything.

The lesson is that a well-defined syntax helps make processing inspectable, but syntax alone does not establish intent or authorization. The fictional team does not claim that a successful parse makes a command safe or useful.

Common misconceptions and mistakes

Context-free means context never matters. It describes rule applicability, not human interpretation.
The grammar and parser are the same object. One defines permissible structure; the other analyzes input using that definition.
Every accepted string makes sense. A grammar can admit semantically implausible combinations.
A CFG always supplies one answer. Ambiguous grammars can license multiple parse trees for a string.

Business use

A CFG can be valuable where explicit syntax, nested structure and reproducible acceptance criteria matter. In a constrained interface, document exactly which expressions the grammar covers and how unsupported input is handled. Include examples that should be rejected as well as accepted.

For natural-language applications, evaluate coverage and ambiguity on representative text. Distinguish a failed parse from a false statement, and distinguish grammatical acceptance from a successful business action. Grammar maintenance becomes an operational responsibility when terminology or allowed commands change. A transparent rule set is useful only if downstream components interpret its output consistently.

Check your understanding

The toy grammar accepts “the report reviewed the analyst.” Does that prove the sentence describes a plausible event?

Answer: No. It proves only that the listed rules derive that string. Plausibility and interpretation require information beyond those rules.

Related terms

Constituency
Parse tree
Ambiguity
Probabilistic context-free grammar
Parsing
production rule
terminal
nonterminal
recursion

Learn next

Draw the parse tree for the worked derivation and mark its two noun phrases. Then study chart parsing to see how a parser can reuse intermediate results when several analyses are possible.

Sources

Jurafsky and Martin, Speech and Language Processing, Chapter 19: https://web.stanford.edu/~jurafsky/slp3/19.pdf. Formal CFG definition, derivations, constituency and parsing. The miniature grammar and business scenario are original teaching examples rather than a deployable English grammar.

Previous: Context encoders Next: Context mixing