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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Regular Languages

  • K. R. Chowdhary

摘要

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.