chapter 11Languages and Automata
Unlearn’d, he knew no schoolman’s subtle art,
No language, but the language of the heart.
Can a machine recognize a language? The answer is “yes” for some machines and for some languages. In this chapter, we’ll study regular languages and context-free languages, together with the machines that recognize them. After discovering that regular languages can be represented by algebraic expressions and by machines called finite automata, we’ll learn how to transform between these representations and how to construct efficient finite automata. We’ll look at some properties of regular languages and examples of languages that are not regular. This sets the stage for studying context-free languages, ...
Get Discrete Structures, Logic, and Computability, 4th Edition 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.
