Logo
☆☆☆☆☆
0.0
Beginner
15h

计算理论

计算机背后的数学原理是什么？计算机语言的理论基础又是什么？通过理解形式语言与自动机模型，我们可以探索这些问题。 在这门全面的课程中，你将学习形式语言、正则语言，以及如何使用相应的自动机模型对它们进行建模。接着，你将掌握正则表达式与文法及其等价关系。随后，你将深入学习上下文无关语言（编程语言的基础）、下推自动机，以及二者之间的关系。在课程后期，你将了解递归可枚举语言、图灵机及其变体、上下文有关语言和无限制文法。 课程结束时，你将深入理解多种形式语言及其对应的自动机模型。此外，由于课程中包含大量练习题，你的理解能力与问题解决能力将得到充分巩固和提升。

11 Lessons
Included in Subscription Plan
Personalized Learning
Powered by AI
View Courses in Subscription
计算理论
计算机背后的数学原理是什么？计算机语言的理论基础又是什么？通过理解形式语言与自动机模型，我们可以探索这些问题。 在这门全面的课程中，你将学习形式语言、正则语言，以及如何使用相应的自动机模型对它们进行建模。接着，你将掌握正则表达式与文法及其等价关系。随后，你将深入学习上下文无关语言（编程语言的基础）...

WHAT YOU'LL LEARN

对形式语言及其结构与性质的深入理解

Content

11 Lessons • 0 Quizzes • 0 Challenges

开始学习
  1. 1

    前置条件与学习目标

  2. 2

    计算导论

  3. 3

    形式语言

  4. 4

    有限状态机

  5. 5

    有限自动机在现实生活中的应用

有限自动机
  1. 1

    确定性有限自动机

  2. 2

    正则语言

  3. 3

    非确定性有限自动机

  4. 4

    NFA与DFA的等价性

  5. 5

    NFA 与补集

  6. 6

    最小自动机

  7. 7

    带输出的机器

  8. 8

    计算机算术

  9. 9

    极简的米利机

正则表达式与文法
  1. 1

    正则表达式

  2. 2

    正则表达式与正则语言的等价性

  3. 3

    正则文法

正则语言的性质
  1. 1

    闭包性质

  2. 2

    判断两种语言相等的决策算法

  3. 3

    其他决策算法

  4. 4

    正则语言的泵引理

  5. 5

    非正则语言

  6. 6

    利用闭包性质证明非正则性

下推自动机
  1. 1

    为有限自动机添加一个栈

  2. 2

    PDA 的示例

  3. 3

    下推自动机与确定性

上下文无关文法
  1. 1

    上下文无关文法简介

  2. 2

    上下文无关文法与推导

  3. 3

    简化文法

  4. 4

    推导树与歧义文法

  5. 5

    PDA与CFG的等价性

  6. 6

    从PDA到CFG（一般情况）

  7. 7

    将PDA转换为CFG的示例（一般情况）

上下文无关语言的性质
  1. 1

    乔姆斯基范式

  2. 2

    乔姆斯基范式规则

  3. 3

    闭包性质

  4. 4

    决策算法

  5. 5

    CFL 是空的还是无限的？

  6. 6

    无限的上下文无关语言与另一个泵引理

  7. 7

    使用上下文无关语言的泵引理示例

图灵机
  1. 1

    图灵机简介

  2. 2

    标准图灵机

  3. 3

    图灵机作为函数

  4. 4

    图灵机作为子程序

  5. 5

    丘奇-图灵论题

  6. 6

    图灵机的变体

  7. 7

    通用图灵机

  8. 8

    非确定型图灵机 = 确定型图灵机

形式语言的概览
  1. 1

    递归可枚举语言

  2. 2

    无限制文法

  3. 3

    无限制文法与图灵机的等价性

  4. 4

    乔姆斯基层级

可计算性
  1. 1

    停机问题

  2. 2

    归约与不可判定性

  3. 3

    瑞斯定理与可判定性

结论
  1. 1

    总结

Certificate of Completion

Showcase your accomplishment by sharing your certificate of completion.

Course Author:Anonymous User

Reviews

Read reviews from students who have taken this course and share your own experience.

Reviews & Comments (0)