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
The statement refuted is: every ambiguous context-free grammar generates an inherently ambiguous language.
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
The displayed grammar is ambiguous: the word has one parse corresponding to and another corresponding to . So the grammar is an ambiguous CFG.
The standard precedence grammar generates the same terminal strings. One inclusion follows by simultaneous induction on its -, -, and -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 , , 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 - and -rules, while the -case is forced by the outer symbols, so the resulting parse is unique. In particular, has only the parse . Thus the language has an unambiguous grammar.
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.
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
- John Watrous, Introduction to the Theory of Computing, Lecture 8 (standard reference, not scraped)