Is a stochastic grammar necessarily context-free?

No. PCFGs are one important family, used here for a concrete explanation.

Can different parses produce the same string?

Yes; that is grammatical ambiguity.

Does a low probability prove an error?

No. It can reflect rarity, model limitations, or an unfamiliar construction.

AI Glossary / Statistics and probability / Intermediate

Stochastic grammar

Definition

A stochastic grammar is a formal grammar augmented with probabilities that describe how its production rules are chosen. It can assign probabilities to derivations and, by combining derivations, to the strings or structures they produce. A common example is a probabilistic context-free grammar, used to model hierarchical structure. The grammar expresses a statistical model of allowed constructions; its probabilities do not by themselves establish the truth, usefulness, or intended meaning of generated content.

What it means

An ordinary grammar describes what can be formed from a start symbol using rules. A stochastic grammar adds a probabilistic account of which permitted alternatives are more likely. It can therefore support generation, ranking, and inference rather than only accept-or-reject judgments.

This entry uses the probabilistic context-free grammar, or PCFG, as its concrete example. Other stochastic grammar families can use different dependencies. In a basic PCFG, a nonterminal's expansion probabilities depend on that nonterminal, not on the complete surrounding sentence. This simplifying assumption makes useful computation possible but can miss important context. A probability assigned to a parse is a model quantity, not automatically calibrated confidence that a human would endorse it.

How it works

Define terminal symbols, nonterminal symbols, a start symbol, and production rules. For a PCFG, assign nonnegative probabilities to alternative rules expanding the same nonterminal so that those probabilities sum to one.

A derivation repeatedly expands nonterminals until only terminals remain. Under the PCFG assumptions, multiply the probabilities of all rule applications to obtain the probability of a particular derivation tree. If several trees produce the same string, sum their probabilities to obtain that string's probability. Maximizing over trees answers a different question from summing over them.

Probabilities may be specified or estimated from suitable training data. With observed parse trees, relative counts of alternative expansions provide a basic estimate. More elaborate learning methods address hidden structure and richer models.

Check termination as well as local probability sums. Recursive grammars can require additional conditions to ensure generation ends with probability one. For parsing, algorithms can reuse subproblem results rather than enumerate every tree. Evaluation should test structural accuracy, coverage, and performance on the intended kinds of input.

Three practical examples

1. A language-processing system ranks alternative grammatical analyses of an ambiguous sentence using a probabilistic parsing model.

2. A test-data generator samples structured commands from a small grammar to exercise a parser while preserving specified syntactic rules.

3. A researcher studies hierarchical symbolic patterns with a probabilistic grammar and checks whether the model captures the relevant dependencies.

Think of it this way

Think of a recipe book where each stage offers alternatives with assigned chances. Multiplying the chosen chances gives the probability of one cooking route. If different routes produce the same finished dish, the dish's total probability includes every route that leads to it.

Worked example

Consider an original terminating toy grammar. The start symbol S becomes A with probability 0.6 or B with probability 0.4. A becomes terminal x with probability 0.5 or terminal y with probability 0.5. B becomes x with probability 0.25 or y with probability 0.75.

Every nonterminal's alternatives sum to one, and every derivation ends after two rules. The tree S → A → x has probability 0.6 × 0.5 = 0.3. The different tree S → B → x has probability 0.4 × 0.25 = 0.1. Therefore the string x has probability 0.3 + 0.1 = 0.4.

For y, the two route probabilities are 0.6 × 0.5 = 0.3 and 0.4 × 0.75 = 0.3, giving total probability 0.6. The two terminal-string probabilities sum to one.

Conditional on observing x, the probability of the A route is 0.3 / 0.4 = 0.75 and that of the B route is 0.25 under this grammar. The most probable x tree has probability 0.3 before conditioning; this differs from x's total probability 0.4. These calculations illustrate model ambiguity and normalization, not natural-language understanding.

Illustrative case study

In a fictional software company, Alder Tools uses a small stochastic grammar to generate test commands for an internal parser. Testers initially select only the most probable derivation for each command and miss alternative structures that produce the same text. The team adds coverage checks for derivation patterns and samples rare permitted branches deliberately. It also tests invalid inputs separately. The grammar provides controlled structured examples, but the team does not equate high generated probability with business importance or assume the generated tests cover every production failure.

Common misconceptions and mistakes

A string probability is not always the probability of its best parse. Ambiguous grammars require summing the probabilities of all relevant derivations for the former quantity.

Local rule probabilities summing to one do not alone guarantee that every recursive grammar terminates almost surely. The grammar's global behavior matters.

More probable does not mean more truthful, more grammatical according to every linguistic theory, or more appropriate for a user. Probabilities reflect the model and training information. A basic PCFG also does not capture every dependency that modern language applications may require. Neural parameterization can change the modeling approach without making these interpretive questions disappear.

Business use

Stochastic grammars can support constrained generation, structured testing, parsing, and interpretable models of symbolic sequences. Their explicit rules make some assumptions easier to inspect than in an unconstrained generator.

Businesses should separate structural validity from semantic and operational validity. A generated command can follow the grammar yet request an inappropriate action. Define coverage goals, evaluate rare cases, and verify any downstream meaning through separate checks. When using a learned grammar, examine how training data and unknown constructions affect both probability estimates and practical coverage.

Check your understanding

Answer: Two derivation trees produce one string with probabilities 0.08 and 0.03, and no others produce it.

What is its probability?

Answer: It is 0.11. The best-tree probability is 0.08, a different quantity.

Related terms

Learn next

Learn context-free parsing and the distinction between best-parse and total-probability algorithms. Then examine how richer grammars relax independence assumptions.

Sources

Michael Collins, Probabilistic Context-Free Grammars, author lecture materials: https://www.cs.columbia.edu/~mcollins/cs4705-spring2019/slides/parsing2.pdf . Core probability, parsing, and termination conditions were consulted. The entry explains the broad term through the PCFG special case; the tiny grammar and fictional testing scenario are original.

Previous: Stochastic gradient Langevin dynamics Next: Stochastic hill climbing