形式语言与自动机是计算机科学中的重要理论基础，主要研究如何用数学模型来描述和处理字符串。第四讲的主题聚焦在有限状态自动机（Finite State Automata, 简称FSA），这是一种能根据有限状态和有限输入进行计算的模型。
有限状态自动机分为确定有限自动机（Deterministic Finite Automata, 简称DFA）和非确定有限自动机（Non-deterministic Finite Automata, 简称NFA）。DFA是其中的一种，它的行为是确定性的，即对于任何给定的状态和输入，下一步的状态是唯一的。而NFA则允许存在不确定性，即在给定状态下，接收到某个输入时，它可以转移到多个不同的状态。
DFA由五个要素构成：
1. **有限状态集**（Finite State Set）：这是DFA中的状态集合，例如Q = {q0, q1, q2, q3}。
2. **有限输入符号集**（Finite Input Alphabet）：这些是机器可以接收的符号，如Σ = {0, 1}。
3. **转移函数**（Transition Function）：δ是一个从状态集和输入符号集的笛卡尔积到状态集的映射，描述了状态如何随输入变化，例如δ(q0, 0) = q2，表示在状态q0时接收到0，会转移到状态q2。
4. **开始状态**（Start State）：DFA开始时所处的状态，例如q0。
5. **终态集合**（Final State Set）：这些是DFA接受的结束状态，例如F = {q0, q3}。
DFA可以通过转移图或转移表来直观表示。转移图中，每个节点代表一个状态，有向边表示状态间的转移，边上的标签是触发转移的输入符号。转移表则是状态和输入的二维表，每一行对应一个状态，每一列对应一个输入，表格中的值是转移后到达的新状态。
DFA接受输入符号串的过程是通过逐步应用转移函数进行的。从开始状态出发，每读取一个输入符号，就根据转移函数更新当前状态。如果最后停在一个终态，那么这个符号串就被DFA接受；否则，它被拒绝。
以给出的DFA为例，如果输入串是001011，DFA将按照以下步骤进行：
1. 开始状态q0，读取0，转移到q2。
2. 在q2，读取0，回到q0。
3. 从q0，读取1，转移到q1。
4. 在q1，读取0，转移到q3。
5. 在q3，读取1，回到q1。
6. 最后读取1，再次转移到q2。
由于最终状态在终态集合内（q2和q3），所以DFA接受输入串001011。
DFA的最小化是将一个DFA转换为具有最少状态数但仍接受相同语言的等价DFA的过程，这有助于简化模型并提高效率。在实际应用中，DFA常用于文本搜索、编译器的词法分析、数据验证等领域，它们能够高效地识别特定模式的字符串。
