Redukce počtu možných derivací
Tvrzení: Nechť G = (N, T, P, S) je BKG.
Následující 3 jazyky jsou totožné:
(1) {w: w Î T*, S Þlm* w}
(2) {w: w Î T*, S Þrm* w}
(3) {w: w Î T*, S Þ* w} = L(G)
Myšlenka: Bez újmy na obecnosti můžeme uvažovat používání pouze nejlevějších nebo nejpravějších derivací.
17/50