Definice: Nechť G = (N, T, P, S) je BKG. Symbol X Î N È T je ukončující, pokud existuje řetězec w Î T*, pro který platí: X
Þ* w.
Jinak X je neukončující.
Příklad:
Pozn.: Každý neukončující symbol může být odstraněn z BKG
Ukončující symboly
Myšlenka: Symbol X je ukončující, pokud X derivuje řetězec terminálů.
Symbol S - ukončující: pro w = a: S Þ1 a
G = ({S, A, B}, {a, b}, {S ® SB, S ® a, A ® ab, B ® aB }, S)
Symbol A - ukončující: pro w = ab: A
Þ1 ab
Symbol B - neukončující: neexistuje w Î T* takové, že: B
Þ* w
Symbol a - ukončující: pro
w = a : a Þ0 a
Symbol b - ukončující: pro w = b : b Þ0 b
28/31