Typ-3-Grammatiken

(= rechtslineare Grammatiken)

jede Regel hat die Form

• Variable → Terminal Variable
• Variable → Terminal
• Variable →ε

(vgl. lineares Gleichungssystem)

Beispiele

• G₁ = ({a, b},{S, T}, S,{S→ε, S→aT, T→bS})
• G₂ = ({a, b},{S, T}, S,{S→ε, S→aS, S→bT, T→aT, T→bS})