Название: Introduction to The Theory of Formal Languages
Автор: Dan A Simovici
Издательство: World Scientific Publishing
Год: 2024
Страниц: 465
Язык: английский
Формат: pdf (true)
Размер: 27.5 MB

Formal language theory is a theoretical discipline in Computer Science that plays a foundational role in areas such as compilers design, programming language theory, information transmission, computational biology, etc.This unique volume is a succinct introduction to formal language theory suitable for an one-semester course. The main focus is on Chomsky's hierarchy of classes of languages ranging from regular languages to context-free, context-sensitive, and recursively enumerable languages. These classes are presented using both generative methods (grammars) as well as various analytical methods including finite automata, pushdown and linearly bounded automata, and Turing machine. The useful reference text contains a large number of exercises of various degree of difficulties and is intended as a textbook for an upper-level undergraduate or a graduate course in formal languages.

We place particular emphasis on context-free languages due to their role in compiler design. This class of languages is introduced using the class of context-free grammars; the devices that provide an alternative characterization of this class, pushdown automata are discussed in the next chapter.

We use labeled Markov algorithms and Turing machines as general abstract models of computation. We cover undecidability results starting with the halting problem for Turing machines and the Post correspondence problem and continuing with undecidability results for various classes of languages. Particular attention is paid in to the class of context-sensitive languages.

The necessary background for a fruitful use of this book consists in general algebra, a familiarity with syntactic definition of programming languages constructs, and some familiarity with discrete mathematics and proofs by induction.




ОТСУТСТВУЕТ ССЫЛКА/ НЕ РАБОЧАЯ ССЫЛКА ЕСТЬ РЕШЕНИЕ, ПИШИМ СЮДА!