1. 引言,有限自动机,正则表达式

1. Introduction, Finite Automata, Regular Expressions

频道:MIT OpenCourseWare · 时长:1:00:34 · 发布:2021-10-06 · 播放:637368

在 YouTube 观看

简介

Michael Sipser 的 MIT 18.404J 计算理论课程的第一讲,涵盖课程机制、有限自动机、正则语言和正则表达式。它证明了正则语言在并集下的封闭性,并开始讨论连接。

HN 为什么推荐

HN 推荐 Sipser 的免费讲座作为标准计算理论教科书的配套,以及理解计算机如何从根本上工作的途径。

Sipser 也有相应的讲座,可以在 YouTube 上免费获取 — HN, 2024

可计算性与复杂性理论 · 大学讲座与课程

中文字幕节选

[吱吱声] [沙沙声] [咔嗒声] 迈克尔·西普瑟:大家好,欢迎 来到2020年秋季在线计算理论导论 课程18.404/6.840。 我叫迈克·西普瑟。 我将是本学期这门课的讲师。 那么让我先告诉大家这门课是关于什么的。 基本上,它将分为两半。 我们将讨论计算机的能力 和局限性——实际上是计算机算法的,计算。 这门课的两个部分大致各占一半。 课程的前半部分将 讨论一个叫做可计算性理论的主题,它 真正问的是原则上你能用算法计算什么。 那是——在20世纪早期是一个活跃的研究领域。 如今作为一个研究主题,它基本上已经关闭了, 主要是因为他们回答了所有重大问题。 所以一个数学领域只有在有 问题要解决时才会保持活力, 而他们确实解决了所有有趣的问题—— 大部分,不是100%。 但大部分在20世纪50年代就差不多结束了—— 再多说一点我们将要讨论的内容。 当你想知道什么样的问题 可以用算法解决——有些你可能 想解决的问题就是无法解决。 例如,给定一个计算机问题的规范, 你想解决,无论那个规范可能是什么—— 比如说你的算法实际上是一个排序算法,例如—— 你想写下那个规范,并有一个自动验证器 来检查一个程序是否满足规范。 嗯,那原则上是不可能的。 你无法制作一个验证器,它会在所有情况下 回答一个程序是否满足某个规范。 所以像这样的事情,我们这学期会证明。 关于数学真理的问题—— 如果给你一个数学陈述,它是真的还是假的? 如果你能写一个计算机程序来回答那个问题,那就太好了。 嗯,如果你是数学家,那就不好了, 因为那会让我们都失业。 但你可以想象那可能是个好东西,但你做不到。 我的意思是,没有算法能回答那个问题。 嗯,在这个过程中,我们将介绍计算模型, 比如有限自动机,我们今天 会看到,图灵机,以及我们沿途会看到的一些其他模型。 课程的后半部分,将在期中考试之后, 我们将换挡,讨论 复杂性理论,它不是看什么 原则上可计算,而是 看什么在实践中可计算,所以是那些 你可以在合理时间内解决的问题。 而且,例如,我相信你们很多人 都知道因数分解问题,它与 RSA密码系统、密码学有关,并问 你是否能快速分解大数。 那是一个我们不知道答案的问题。 我们就是不知道如何快速分解大数。 但有可能存在我们尚未发现的算法 可以做到这一点。 它与计算机科学交叉领域中这个非常著名的问题有关 以及数学中称为P与NP问题的交叉领域,你们很多人可能听说过。 我们会讨论这个问题。这学期我们会花很多时间在这上面。 在此过程中,我们会讨论不同的度量方式, 关于复杂性、计算、时间和空间, 时间和内存,理论内存,电子空间。 这将是课程中复杂性理论部分的重要部分—— 介绍其他计算模型, 比如概率计算和交互式计算。 谈谈课程的期望。 首先,先修课程。 列出了一堆先修课程,6.042, 18.062,或者可能还有其他科目。 真正重要的是,这是一门数学课。

HN 上的讨论

在我知道的大多数书里,这只是一半的章节。或者说是这个1小时MIT视频[0]的一个子集,但讲师还解释了有限自动机,这是完成所有事情的基本机制。[0]: [VIDEO] — skydhash, 2025-08
> 如果你要求括号平衡,那就不再是正则语言了。今天我学到了:[LINK] 作为一个最近才学到正则语言形式定义的人(感谢 [VIDEO],最近在这个板上提到),我对这个的形式证明很感兴趣?直觉上感觉是真的,但我还没完成课程,因此还没遇到,也还不能很好地推理。那么问题是不是在于试图“编码”括号是否平衡时,我们需要无限“层级”来表示我们打开了多少括号而不是关闭了多少(即一个栈),而这违反了有限自动机的有限性?所以我现在谷歌了一下,发现这个结果是由于“泵引理”:[LINK] — eterm, 2025-06
正如其他人已经说过的:Sipser 的《计算理论》是这方面的首选入门书。我建议真的从头到尾读一遍这本书。它有助于全面了解进入复杂性理论之前的所有内容。Sipser 也有相应的讲座,可以在 YouTube 上免费观看:[VIDEO]。 — sky2224, 2024-06
AI 永远无法教授数学,因为 AI 无法推理。它处理信息的方式与人类截然不同。它充其量只是一个有缺陷的预言机,可能会通过遗漏来撒谎,而你却无法察觉。这得到了计算存在硬性限制这一事实的支持,无论是在可计算性理论还是复杂性理论方面,这些限制常常被新手和魔法思维者忽视,尽管这些领域在很大程度上已被计算机科学专家解决,至少在可计算性理论方面是如此。大部分工作是在 1950 年代完成的。这不是一个困难的学科,但大多数网上的人就是不愿意花功夫理性地学习它,而是选择试图隐藏自己的无知,因为他们感到不足,或者也许他们在从事更恶意的行为。推理(虚假的正当理由)并不重要。然而,当专家们已经验证了这些事情,而任何与叙事相反的提及都会在公共论坛上引发 downvote 以将其从视野中移除时,这很能说明问题。这是第三方故意采取行动试图误导他人关于风险的完美例子(这些方的行为移除了合法和有效的信息)。对于那些有胆量… — trod123, 2024-06
他在第一讲中特别提到了先修要求,在这个时间戳:[VIDEO](你应该能够轻松理解数学定理并写出证明。) — kjhughes, 2021-10

相关视频