Definice: Nechť L je jazyk. L je bezkontextový jazyk
(BKJ), pokud existuje bezkontextová gramatika,
která generuje tento jazyk L.
Příklad:
L = {anbn: n ³ 0}
je bezkontextový jazyk.
Bezkontextový jazyk (BKJ)
Myšlenka: Jazyk generovaný bezkontextovou
gramatikou
G = (N, T, P, S), kde N = {S}, T = {a, b},
P = {1: S ® aSb, 2: S ® e}
S Þ aSb [1] Þ aaSbb [1] Þ aabb [2]
…
L(G)
9/50