John Watrous 《Introduction to the Theory of Computing》13 -- 图灵机的变体

Posted on 2021-02-07 | | Visitors:

前言

这节课我们将会继续讨论图灵机模型，着重于讲改变模型而又不影响它们能力的方法。

John Watrous 《Introduction to the Theory of Computing》12 -- 图灵机

Posted on 2021-01-26 | | Visitors:

前言

在本节课中我们将会讨论图灵机计算模型。Alan Turing（1912-1954）在1963年提出了这个模型，并且以他的名字命名。Alan Turing对于本课程的影响怎么说都不会夸张 — 理论计算机科学的发展实际就是从图灵的工作开始的，并且由于这个原因他时常被称作理论计算机科学之父。

John Watrous 《Introduction to the Theory of Computing》11 -- 下推自动机

Posted on 2020-12-28 | | Visitors:

前言

这节课使我们讲解上下文无关语言的最后一节了。但是往后的课程的内容中我们会不时地参考上下文无关语言，就行正则语言那样。
　　本节课的第一部分我们讲下推自动机的计算模型，它为了我们提供了可供选择的基于CFG的上下文无关语言的定义描述。第二部分我们谈一下至今都还未讨论过的一些上下文无关语言的属性，而且他们有助于理解下推自动机。

John Watrous 《Introduction to the Theory of Computing》10 -- 证明非上下文无关语言

Posted on 2020-12-16 | | Visitors:

前言

这节课我们会学习一种方法，通过它我们可以证明非上下文无关语言。这个方法你会觉得非常熟悉，因为它和我们在第5节课证明非正则语言的方法是类似的。

John Watrous 《Introduction to the Theory of Computing》09 -- 上下文无关语法的属性

Posted on 2020-12-16 | | Visitors:

前言

这节课我们会检验上下文无关语言类的一些属性，包括它在正则运算下是闭合的，每个正则语言都是上下文无关的，以及一个上下文无关语言和一个正则语言的交集总是上下文无关的。

John Watrous 《Introduction to the Theory of Computing》08 -- 分析树、歧义性和乔姆斯基范式

Posted on 2020-11-29 | | Visitors:

前言

这节课我们会讨论一些有关于上下文无关语法的重要概念，包括分析树、歧义性，还有一种特殊形式的上下文无关语法，被称为乔姆斯基范式。

John Watrous 《Introduction to the Theory of Computing》07 -- 上下文无关语法和语言

Posted on 2020-11-15 | | Visitors:

前言

接下来在本课程中我们将要学习的语言类是上下文无关语言类，它是由上下文无关语法的概念来定义的，简称CFG。

John Watrous 《Introduction to the Theory of Computing》06 -- 正则语言的进一步证明

Posted on 2020-11-08 | | Visitors:

前言

这节课我们会讨论一些额外的运算，它们对于正则语言是闭合的，并且复习一些关于正则语言的案例问题。这是本堂课着重讲正则语言的最后一节课，但是我们会频繁回顾这些知识点，在往后的课程中它们将与不同的计算模型和语言类关联。

John Watrous 《Introduction to the Theory of Computing》05 -- 证明非正则语言

Posted on 2020-11-06 | | Visitors:

前言

我们已经知道对于任意字母表$\Sigma$存在语言$A\subseteq \Sigma^{*}$是非正则的。这是因为基于$\Sigma$的语言数量是不可数的，但是基于$\Sigma$的正则语言是可数的。然而这个观察结果不足以让我们推导出某个非正则语言是非正则的。本节课我们会讨论一种方法，它可以证明相当广泛的语言是非正则的。

John Watrous 《Introduction to the Theory of Computing》04 -- 正则运算和正则表达式

Posted on 2020-10-25 | | Visitors:

前言

这节课我们会讨论正则运算和正则表达式，以及它们和正则语言之间的关系。