Linksrekursion (II)

Def: CFG G = ($\Sigma$, V, S, R) ist in Greibach-Normalform, falls für jede Regel (l$\to$r) $\in$ R gilt: r $\in$ $\Sigma$V^*.

möglich ist auch: ... r $\in$ $\Sigma$(V $\cup$ $\Sigma$)^*

Satz: zu jeder CFG G gibt es eine CFG G' in Greibach-Normalform mit L(G) $\setminus$ $\epsilon$ = L(G').

Aufgaben (evtl. autotool): Greibach-Normalform von

• ({a, b},{S, T}, S,{S$\to$TS | b, T$\to$ST | a})
• ({a, b},{S, T}, S,{S$\to$TT | b, T$\to$SS | a})