什么是计算理论？

• 抽象计算模型的研究
• 专注于理解计算的极限
• 衍生赢博体育程序：正则表达式、解析

一个计算过程的抽象模型

• 该过程将一系列符号作为输入。
• 该过程产生一系列符号作为其输出。

更多关于符号序列的内容

• 字母表Σ是一组符号。
• 从字母表中选出的符号序列就是字符串。
• 计算使用输入字母Σ_输入和一个输出字母表Σ_输出。这些字母可能是相同的，也可能不同。
• 宇宙是由字母表组成的赢博体育可能的字符串的集合。

一种决策算法

• 这是一种更简单的计算过程，也更容易学习。
• 决策算法仍然丰富到令人感兴趣。
• 由于这种类型的算法只处理输入，我们只需要担心输入字母Σ。

语言和决策者

• 语言是由输入字母Σ组成的一组字符串。
• 语言通常是Σ生成的字符串的子集。
• 给定一种语言L，当且仅当其输入x∈L产生输出时，算法决定该语言。

有限状态机

Σ = {0,1}

L = {x | x包含奇数个1}

另一个例子

L = {x | x包含子字符串010}

正式的定义

有限自动机是一个元组{Q， Σ， δ, q0, F}，其中

1. Q是一个叫做状态的有限集合，
2. Σ是一个有限集合，叫做字母表，
3. δ: Q × Σ→Q为过渡函数，
4. 问₀ ∈ 问是开始状态,
5. F是可接受状态的集合。

如果某个有限自动机M能够识别语言L，那么语言L就是正则语言。