Chapter 2Automata and Grammars
Indisputably, the notion of a procedure is central to computation and, consequently, computer science as a whole. We surely agree that it consists of finitely many instructions, each of which can be executed mechanically in a fixed amount of time. When running, it reads input data, executes its instructions, and produces output data. Nevertheless, apart from understanding this notion intuitively, we need its formalization in order to obtain a systematized body of mathematically precise knowledge concerning it. Therefore, the theory of computation has developed an important field, called formal language theory, which formalizes the notion of a procedure by a large variety of language models. Despite their diversity, ...
Get Jumping Computation now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
