Hlavní rozhodnutelné problémy
1. Problém členství:
• Instance: BKG G, w Î S*; Otázka: w Î L(G)?
2. Problém prázdnosti:
• Instance: BKG G; Otázka: L(G) = Æ?
3. Problém konečnosti:
• Instance: BKG G;    Otázka: Je L(G) konečný?
25/31