Main Decidable Problems
1. Membership problem:
• Instance: CFG G, w Î S*;Question: w Î L(G)?
2. Emptiness problem:
• Instance: CFG G; Question: L(G) = Æ?
3. Finiteness problem:
• Instance: CFG G; Question: Is L(G) finite?
25/31