Alphabeta Math
False statementConstruction: Literature-sourcedVerification: AI-generatedprecheck passaudited 2026-08-30
How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

  • Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
  • AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
  • AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

FALSE: an ambiguous CFG always generates an inherently ambiguous language

Statement

False claim: if a context-free grammar is ambiguous, then the language it generates is inherently ambiguous.

Facts & Assumptions

Given: The grammar EE+EEE(E)ab.

[A1]

The statement refuted is: every ambiguous context-free grammar generates an inherently ambiguous language.

[L1]

A context-free language is inherently ambiguous when every context-free grammar generating it is ambiguous, by Ambiguous grammars, unambiguous grammars, and inherently ambiguous languages.

Refutation

technique · direct
1.1

The displayed grammar is ambiguous: the word a+aa has one parse corresponding to a+(aa) and another corresponding to (a+a)a. So the grammar is an ambiguous CFG.

given
1.2

The standard precedence grammar EE+TT,TTFF,F(E)ab generates the same terminal strings. One inclusion follows by simultaneous induction on its E-, T-, and F-derivations, since every displayed production can be simulated by the first grammar. For the reverse inclusion, scan a generated word at parenthesis depth zero: if there is a +, split at the rightmost such +; otherwise, if there is a *, split at the rightmost such *; the remaining factor is either a, b, or a parenthesized expression. Induction on the word length gives a derivation in the precedence grammar. These rightmost top-level splits are forced by its left-recursive E- and T-rules, while the F-case is forced by the outer symbols, so the resulting parse is unique. In particular, a+aa has only the parse a+(aa). Thus the language has an unambiguous grammar.

giveninduction
2.1

By [L1], a language with an unambiguous grammar is not inherently ambiguous. So the ambiguous grammar from step 1.1 does not force its language to be inherently ambiguous, and [A1] is false.

A1L1step 1.1step 1.2

Depends on

Used by

Dependency tree · two levels

3 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources