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