Definice:
Jazyk
L
je
konečný
, pokud
L
obsahuje
konečný počet řetězců, jinak je
nekonečný.
Pozn.:
Nechť
S
je množina
;
c
ard(
S
)
značí počet prvků v
S
Příklad:
•
L
1
=
Æ
je
konečný jazyk
, protože card
(
L
1
) =
0
•
L
2
=
{
e
}
je
konečný jazyk
, protože
card
(
L
2
) =
1
•
L
3
=
{
x
:
|
x
|
= 1
}
=
{0, 1}
je
konečný jazyk
,
protože card
(
L
3
) =
2
•
L
4
=
{
x
:
10
je podřetězec
x
} = {10, 010, 100, … }
je
nekonečný jazyk
Konečné a nekonečné jazyky
Myšlenka:
Konečný jazyk obsahuje konečný
počet řetězců
12/20