Regular Languages
摘要
In certain classRegular languages of problems, including sequential circuits, lexical analyzers, text processing, and pattern recognition, the first step is to obtain the circuit’s behavior or the pattern of text in the form of a regular expression. Richer the description in the form of regular expression, easier it is to write the problem specifications. The regular expressions, finite automata, and regular languages are isomorphic to each other, thus a problem can be solved in any one platform and can be transformed into the other. This chapter presents many important closure properties of regular languages, conversion from regular expressions to finite automata and vice versa, the concerning theorems and examples, and many approaches to understand the famous pumping lemma and worked out problems related to pumping lemma, its limitations, and Myhill–Nerode theorem that overcomes that limitation of pumping lemma. In addition, many approaches are presented to deduce a regular expression for a given finite automata. The chapter concludes with self-review questions, practice exercises, and references to important resources.