Kontextové
jazyky
Závěr: Fundamentální modely pro kontextové jazyky jsou:
1) Kontextové gramatiky
2)
Lineárně
ohraničené automaty
Definice: Nechť L je jazyk. L je kontextový
jazyk, pokud existuje lineárně ohraničený automat M takový, pro který platí: L = L(M).
33/45
Tvrzení: Pro každou KG G existuje LOA M,
pro který platí: L(G) = L(M).
Důkaz: Viz. str. 732 v knize [Meduna: Automata and
Languages]
Tvrzení: Pro každý LOA M, existuje
KG G, pro kterou platí: L(M) = L(G).
Důkaz: Viz. str. 734 v knize [Meduna: Automata and
Languages]