The CFG Complexity of Singleton Sets

Lance Fortnow, William Gasarch

Let G be a context-free grammar (CFG) in Chomsky normal form. We take the number of rules in G to be the size of G. We also assume all CFGs are in Chomsky normal form. We consider…