PPL 121 / 177 permanent IDsPrize Problem Ledger · PPLChecked 2026.07.27
Prize Problem LedgerOkhotin grammar problemsPPL 121Okhotin · Collapse of the Boolean LL(k) hierarchy

Permanent problem IDPPL 121

Reconfirm sponsorIndependentconjecture

Formal languages

Okhotin · Collapse of the Boolean LL(k) hierarchy

Is there a fixed k₀ such that Boolean LL(k) grammars generate the same language family as Boolean LL(k₀) grammars for every k≥k₀?

Boolean grammarsconjunctive grammarstheoretical computer science
01

The problem

Is there a fixed k₀ such that Boolean LL(k) grammars generate the same language family as Boolean LL(k₀) grammars for every k≥k₀?

Open since2007original problem survey
Last checked2026.07.27Catalog verification
02

Reward offers

Offer 01C$360Alexander Okhotin
Personal offer

Okhotin’s 2010 author update raises the award for the first correct solution of each remaining problem to C$360 and says the original terms remain in force. Because the primary terms page has not been refreshed since 2010, confirm claim procedure with the sponsor.

03

Sources & reading