Is a discovery procedure necessarily a computer program?

No. In its linguistic use, it can describe an explicit methodological procedure; some such methods can be implemented computationally.

Is every parser a discovery procedure?

No. A parser may simply apply a fixed grammar to an input sentence without discovering the grammar itself.

Does substitution reveal the whole grammar?

No. It can provide evidence about grouping and distribution, but one diagnostic does not establish a complete, uniquely determined analysis of a language.

AI Glossary / Natural language and speech / Intermediate

Discovery procedure

Definition

In the linguistic context of this glossary, a discovery procedure is a systematic method intended to derive a description of a language's structure from linguistic evidence. The term is associated with historical efforts to make grammatical analysis explicit and reproducible. It is not a general label for business discovery, search engines, or scientific discovery by AI.

What it means

A linguist observing utterances must decide which words belong together and what patterns describe their arrangement. A discovery procedure attempts to specify how those decisions should be reached, rather than leaving them entirely to unrecorded intuition.
One historically important idea is substitution: if a group of words can occur where a simpler unit can occur, that provides evidence that the group behaves as a constituent. The procedure connects observable distribution with a proposed grammatical analysis.
The ambition of a fully general discovery method is stronger than demonstrating one useful diagnostic. A small successful example does not prove that a method uniquely recovers the complete grammar of every language.

How it works

A procedure starts from defined evidence, such as a set of utterances and judgments about possible substitutions. It applies explicit operations or tests and records the resulting structural hypotheses.
For a constituency-oriented exercise, an analyst can identify candidate spans, replace them with simpler expressions, and compare the resulting sentences. Repeated patterns across contexts can support a proposed category or grouping.
The method's assumptions matter. The available data, admissible tests, treatment of ambiguity, and chosen grammatical formalism all influence the result. A parser that applies an already supplied grammar performs a different task from a procedure intended to discover that grammar from evidence.

Three practical examples

A linguistics class uses substitution tests to investigate whether a multiword expression behaves as one grammatical unit.
A grammar-induction project documents what evidence and assumptions its learning procedure uses before claiming to recover structure automatically.
An NLP team reviewing a rule-based parser separates manually supplied grammar rules from patterns inferred from training examples.

Think of it this way

Think of writing a reproducible recipe for investigating how unfamiliar components fit together. The recipe specifies the tests and the observations that support each grouping. The analogy captures methodical inference, but language data can support several analyses, and successful local tests do not guarantee one universally correct structural description.

Worked example

Consider an invented classroom dataset: “The experienced analyst arrived,” “The analyst arrived,” and “She arrived.” An analyst proposes that “the experienced analyst” forms a unit because it can be replaced by “she” in this sentence frame.
The same candidate appears in another frame: “We interviewed the experienced analyst.” Replacing it with “her” yields “We interviewed her.” This second context adds evidence that the multiword expression behaves as a noun phrase, while the changed pronoun form reflects its grammatical role.
Now try replacing only “experienced analyst” with “she” while leaving the determiner: “The she arrived.” Under the ordinary reading intended here, that is not an acceptable substitution. The failure cautions against treating every substring as the same kind of constituent.
This exercise illustrates one diagnostic and its interpretation. It does not supply a complete grammar, establish all possible constituents, or eliminate the need to consider context and additional tests. The proposed grouping is a hypothesis supported by the selected examples.

Illustrative case study

Fictional case: SyntaxWorkshop teaches language analysis through an interactive notebook. The initial lesson labels every successful replacement as definitive proof of a constituent. Reviewers notice that students begin treating the test as an infallible algorithm for all constructions.
The revised lesson records the sentence frame, replacement expression, acceptability judgment, and interpretation. It asks students to compare additional contexts and distinguishes supporting evidence from a claim of complete grammatical discovery.
For a later machine-learning exercise, the team also states which categories are supplied in advance. This fictional case illustrates clearer methodology and reporting; it does not claim that the lesson solves the historical problem of discovering a language's grammar.

Common misconceptions and mistakes

Do not confuse discovering a grammatical description with parsing a sentence using one already provided.
Do not treat the term as a promise that raw text alone always determines a unique grammar. A method's assumptions and evidence must be specified.
Avoid turning one substitution success into a universal conclusion. Linguistic diagnostics can depend on the construction and intended interpretation. Also distinguish the historical technical sense here from ordinary organizational discovery processes.

Business use

The term is mainly useful for understanding the intellectual background of grammar induction and structural language analysis. For business teams evaluating language technology, its practical value is the demand for clarity about what the system actually learns and what humans have already supplied.
A project description should identify the input evidence, predefined categories, decision procedure, and evaluation target. That makes claims such as “the system discovers structure” more reviewable. A useful demonstration shows both successful examples and cases outside the method's stated scope.

Check your understanding

A tool accepts a hand-written grammar and returns a parse tree for each sentence. Has that demonstration alone shown that it can discover the grammar from raw language data?

Answer: No. The grammar was supplied as an input. Demonstrating discovery would require a separate account of how the grammatical description is inferred and evaluated.

Related terms

Grammar induction
Constituency
Syntactic parsing (computational linguistics)
Phrase structure grammar
distributional analysis
substitution test
syntactic parsing
grammatical inference

Learn next

Compare a parser with a grammar-induction system and list which inputs each receives. Then carry out several constituency diagnostics on the same phrase, recording the evidence and the limits of each inference.

Sources

Sources: Jurafsky and Martin, Speech and Language Processing, Constituency Grammars, historical notes and constituency discussion, archived author draft: https://web.stanford.edu/~jurafsky/slp3/old_feb24/D.pdf Historical notes on page21 and the constituency evidence discussion were independently consulted. The original substitution exercise is a limited diagnostic, not a universal grammar-discovery claim.

Previous: Discourse relation Next: Discovery system (artificial intelligence)