Grammaires hors-contexte

def.: Une grammaire est une grammaire hors-contexte si toutes les règles sont de la forme A → B, A ∈ V − Σ, B ∈ V^{∗}.

exe.: La grammaire G_{1} = ({S, a, b}, {a, b}, R_{1}, S), R_{1} = {S → aSb, S → ε}, est hors-contexte et génère le langage {a^{n}b^{n}/n ≥ 0}.

exo.: Décrire la grammaire qui génère le langage {ww^{R}}.