Algori
tmus
:
Problém konečnosti
•
Vstup:
BK
G
G
= (
N
,
T
,
P
,
S
)
;
•
Výstup:
ANO
, pokud
L
(
G
)
je
konečný
N
E
,
pokud
L
(
G
)
je nekonečný
•
Metoda:
•
Nechť
k
=
2
card(
N
)
•
if
exist
uje
z
Î
L
(
M
),
k
£
|
z
| <
2
k
then
napiš
(’
N
E
’)
else
napiš
(’
ANO
’)
Problém konečnosti je pro BKJ rozhodnutelný
Celkově:
30
/31