The previous chapter introduced the deterministic and nondeterministic finite automata (DFA and NFA) and regular expressions, all of which define the class of regular languages. In that chapter, we learned that the class of regular languages is closed under all set operations, concatenation, and the Kleene-star. This chapter studies the limitations of regular languages by showing that they capture only a fraction of all languages.

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

Non-regularity

  • Mitsunori Ogihara

摘要

The previous chapter introduced the deterministic and nondeterministic finite automata (DFA and NFA) and regular expressions, all of which define the class of regular languages. In that chapter, we learned that the class of regular languages is closed under all set operations, concatenation, and the Kleene-star. This chapter studies the limitations of regular languages by showing that they capture only a fraction of all languages.