6533b82efe1ef96bd12944e2
RESEARCH PRODUCT
Elements of Language Theory
Eljas Soisalon-soininenSeppo Sippusubject
Class (computer programming)ParsingProgramming languageComputer scienceObject language020207 software engineering0102 computer and information sciences02 engineering and technologyDecision problemcomputer.software_genre01 natural sciencesPicture languageLinguisticsPhilosophy of language010201 computation theory & mathematicsFormal language0202 electrical engineering electronic engineering information engineeringRewritingcomputerdescription
In this chapter we shall review the mathematical and computer science background on which the presentation in this book is based. We shall discuss the elements of discrete mathematics and formal language theory, emphasizing those issues that are of importance from the point of view of context-free parsing. We shall devote a considerable part of this chapter to matters such as random access machines and computational complexity. These will be relevant later when we derive efficient algorithms for parsing theoretic problems or prove lower bounds for the complexity of these problems. In this chapter we shall also discuss a general class of formal language descriptors called “rewriting systems” or “semi-Thue systems”. Later in the book we shall consider various language descriptors and language recognizers as special cases of a general rewriting system. As this approach is somewhat unconventional, we advise even the experienced reader to go through the definitions given in this chapter if he or she wishes to appreciate fully the presentation in this book.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1988-01-01 |