LearnLog

CH3 Regular Expressions and Languages

学习课程"形式语言与自动机"时做的笔记, 内容主要来自 Automata Theory, Languages, and Computation一书的第三章. 主要是关于RE的内容.

前面我们了解了DFA, NFA, ϵ\epsilon-NFA, 并对它们的等价性做了分析. 在这个过程, 我们大量地应用了归纳的定义与证明.

现在, 我们将引入一种新的符号RE, 并且证明这种符号所表达的语言集合, 与DFA, NFA等自动机所表达的集合是等价的.

CH4 Properties of Regular Languages

The Pumping Lemma

closure property

decision properties

  • 语言是任意的, 没有一种通用的有穷符号能够对任意的语言进行表达.
  • RE是可判定的, 而许多强于RE的语言是不可判定的.
backtop