Open AccessContext-Free Grammars with Graph Controlled Tables
Author(s) -
Grzegorz Rozenberg,
Arto Salomaa
Publication year - 1975
Publication title -
daimi pb
Language(s) - English
Resource type - Journals
eISSN - 2245-9316
pISSN - 0105-8517
DOI - 10.7146/dpb.v4i43.6463
Subject(s) - tree adjoining grammar , l attributed grammar , context free grammar , context sensitive grammar , rule based machine translation , computer science , indexed grammar , graph , phrase structure grammar , grammar , extended affix grammar , embedded pushdown automaton , programming language , natural language processing , theoretical computer science , linguistics , philosophy
It is shown that every context-sensitive language can be generated by a context-free grammar with graph control over sets of productions. This can be done in two different ways, corresponding to unconditional transfer programmed grammars and programmed grammars with empty failure fields. Also some results concerning ordinary programmed grammars are established.