A unified approach to the generation and the acception of formal languages
Acta Informatica - 1978
Tóm tắt
The duality of generation and acception of the Chomsky classes of languages is emphasized by considering the corresponding acceptors as Semi-Thue-Systems instead of unnatural “machines”. It is shown as one main result that lba's, pda's and fsa's are characterized by imposing extremely simple and natural length conditions on the productions of the accepting Semi-Thue-System. As a second result, the shift-reduce or LR-acceptor which is wellknown from syntax analysis is generalised for CH-1 and CH-0 languages. As for contextfree languages, the LR-acceptor when scanning a word from Left to right yields a Right-most derivation in the general sense.
Từ khóa
Tài liệu tham khảo
Büchi, J.R.: Regular canonical systems and finite automata. University of Michigan. Ann Arbor. Technical Report, 1959
Büchi, J.R.: Regular canonical systems. Arch. Math. Logik Grundlagenforsch. 6, 91–111 (1964)
Cannon, R.L.: State grammar parsing. PhD. Thesis, Univ. North Carolina. Chapel Hill, 1973
Deussen, P.: Strategies in acceptors and their relation 10 LR(k)-LL(k)-Theories. Interner Bericht Nr. 8 77. Fakultät für Informatik, Universität Karlsruhe, 1977
Goos, G.: Überselzerbau. Manuscript (to be published)
Hotz, G.: Eindeutigkeit und Mehrdeutigkeit formaler Sprachen. Elektron. Informationsverarb. Kybernetik 2. Heft 4, 235–246 (1966)
Hotz, G., Claus, V.: Automatentheorie und formale Sprachen. III. Formale Sprachen. BI, Hochschulskriptum, 1972
Hopcroft, J.E., Ullman, J.D.: Formal languages and their relation to automata. Reading, Massachusetts: Addison-Wesley 1969
Kasai, T.: A hierarchy between context-free and context-sensitive languages. J. Comput. System Sci. 492–508 (1970)
Langmaack, H.: Zur Äquivalenz der Hotzschen und Paulschen Definition der Mehrdeutigkeit von Chomsky-Sprachen. In: 4. Kolloquium über Automatentheorie, Erlangen, 1967
Langmaack, H.: Application of regular canonical systems to grammars translatable from left to right. Acta Informat. 1, 115–138 (1971)
Langmaack, H., Eickel, J.: Präzisierung der Begriffe Phrasenstruktur und strukturelle Mehrdeutigkeit in Chomsky-Sprachen. In: 3. Kolloquium über Automatentheorie. Basel: Birkhäuser 1967
Langmaack, H., Schmidt, G.: Klassen unwesentlich verschiedener Ableitungen als Verbände. Tagungsbericht Automatentheorie und Formale Sprachen, BI, 1970
Nelson, R.J.: Introduction to automata. New York: Wiley 1968
Salomaa, A.: Formal languages. New York: Academic Press 1973