Finite State Machine (FSM) Finite Automata (FA)

Review: some basic concepts

<aside> 💡

Program: strings in specific symbols

</aside>

<aside> 💡

Grammar: a set of rules to generate a well-formed program by using it

</aside>

Review: basic function and hierarchy

• Program

<aside> 💡

describe the processing procedures for certain data

</aside>

• Function of program languages
  • Describe data and the processing procedures of data
• Hierarchy of program
  • subprogram, process, function
  • object-oriented: class
  • sentence: expression

这段文字描述了有限状态机（Finite State Machine, FSM）和有限自动机（Finite Automata, FA）的基本功能和层次结构，并且提到了程序语言的功能及其层次结构。以下是详细的解读：

有限状态机（FSM）和有限自动机（FA）

基本功能

• 有限状态机（FSM）：FSM 是一种数学模型，用于描述系统在不同状态下对外部输入信号的响应。FSM 通常用于建模控制系统、协议、算法等，特别是在编译器的词法分析器（扫描器）中用于识别标记（tokens）。
• 有限自动机（FA）：FA 是一种特殊的 FSM，用于识别特定类型的字符串集合。FA 可以分为确定性有限自动机（Deterministic Finite Automaton, DFA）和非确定性有限自动机（Nondeterministic Finite Automaton, NFA）。

层次结构

• FSM 和 FA 在编译器中的应用：在编译器中，FSM 和 FA 主要应用于词法分析阶段。词法分析器通过识别源代码中的标记（tokens），将源代码转换成编译器可以处理的形式。FSM 和 FA 提供了一种高效的方式来识别这些标记。

程序语言的功能

描述数据和数据处理过程

• 程序语言的功能：程序语言是用来描述数据及其处理过程的工具。通过程序语言，开发者可以定义数据结构、算法和逻辑流程，从而实现所需的功能。

程序的层次结构

层次结构示例

• 子程序（Subprogram）：子程序是一段独立的代码，可以被多次调用。子程序可以是函数或过程，通常用于封装特定的功能。
• 进程（Process）：进程是一个正在执行的程序实例，拥有自己的地址空间和系统资源。进程可以并发执行，并通过进程间的通信（IPC）机制进行协调。
• 函数（Function）：函数是一种常见的子程序类型，用于封装一段可重复使用的代码。函数通常接受输入参数，并返回结果。
• 面向对象：类（Class）：在面向对象编程中，类是对象的模板，定义了对象的属性和方法。类提供了封装、继承和多态等特性。
• 句子（Sentence）：表达式（Expression）：在编程语言中，表达式通常是一个产生值的代码片段。表达式可以是简单的，如一个变量或常量，也可以是复杂的，如涉及多个操作数和运算符的组合。

示例

FSM 和 FA 在词法分析中的应用

假设我们要编写一个简单的词法分析器来识别整数常量、标识符和关键字。我们可以使用 FSM 或 FA 来描述这个过程：

1. 整数常量识别：
   • 初始状态为 S0。
   • 如果读到数字（0-9），转移到下一个状态 S1 并继续读取。
   • 如果读到非数字，则结束整数常量的识别。
2. 标识符识别：
   • 初始状态为 S0。
   • 如果读到字母（a-z, A-Z）或下划线（_），转移到下一个状态 S2 并继续读取。
   • 如果读到数字（0-9），保持在状态 S2 并继续读取。
   • 如果读到非字母和非数字，则结束标识符的识别。
3. 关键字识别：
   • 初始状态为 S0。
   • 如果读到特定的关键字序列（如 if, else, while 等），则识别为关键字。

程序的层次结构示例

假设我们有一个简单的 C++ 程序：

#include <iostream>

// 函数定义
int add(int a, int b) {
    return a + b;
}
// 类定义
class SimpleMath {
public:
    int multiply(int a, int b) {
        return a * b;
    }
};
int main() {
    // 调用函数
    int sum = add(3, 4);
    std::cout << "Sum: " << sum << std::endl;
    // 创建类的实例
    SimpleMath math;
    int product = math.multiply(3, 4);
    std::cout << "Product: " << product << std::endl;
    return 0;
}

在这个例子中：

• 函数：add() 是一个简单的函数，用于计算两个整数的和。
• 类：SimpleMath 是一个简单的类，包含一个成员函数 multiply()，用于计算两个整数的乘积。
• 主函数：main() 是程序的入口点，调用了前面定义的函数和类的成员函数。

总结

• 有限状态机（FSM）和有限自动机（FA）：主要用于建模控制系统、协议、算法等，特别是在编译器的词法分析器中用于识别标记。
• 程序语言的功能：描述数据及其处理过程。
• 程序的层次结构：包括子程序、进程、函数、类等，用于组织代码和实现功能。

通过这些层次结构，程序语言可以更好地组织和描述数据处理过程，使得程序更加模块化、可读性和可维护性更强。

Some basic terms

Alphabet table:

<aside> 💡

a set of non-empty finite elements (symbols), written by $∑$

• {a, b, c, +, …}

</aside>

Every element in the table called string

• String in $∑$: any finite sequence consisted of symbols in $∑$
• Null sequence: a sequence not including any string
  • Empty string $ε$, is also a string of $∑$
• $∑$*, all strings, including ε

这段文字介绍了几种基本术语，特别是关于符号集（Alphabet）和字符串（String）的概念。以下是详细的解读：

符号集（Alphabet）

定义

• 符号集：符号集是一个非空的有限元素集合，通常用希腊字母$∑$ 来表示。符号集中的元素称为符号（Symbols）。

示例

• 符号集 $\Sigma$：一个符号集可以表示为 $\{a, b, c, +, \ldots\}$。这里的 $\ldots$ 表示还有其他符号，具体取决于上下文。

字符串（String）

定义

• 字符串：在符号集 $\Sigma$中，任何由符号集中的符号组成的有限序列称为字符串（String）。

示例

• 字符串：如果 $\Sigma = \{a, b, c, +, -\}$，则以下是一些字符串的例子：
  • $ab$
  • $abc$
  • $++-$

特殊字符串：空序列和空字符串

• 空序列：一个不包含任何符号的序列称为空序列（Null Sequence）。
• 空字符串：空字符串（Empty String）通常用 $\epsilon$ 表示，它是符号集中的一种特殊字符串，长度为零。尽管空字符串没有实际的符号，但它仍然是 $\Sigma$ 中的一个字符串。

所有可能的字符串集合：$\Sigma^*$

• $\Sigma^*$：$\Sigma^$ 表示所有可能的字符串的集合，包括空字符串 $\epsilon$。$\Sigma^$ **包含了符号集 $\Sigma$ 中所有可能的字符串，不论长度。

示例

• $\Sigma^*$：如果 $\Sigma$ $= \{a, b, c, +, -\}$，则 $\Sigma^*$ 包含以下字符串：

总结

• 符号集（Alphabet）：符号集是一个非空的有限元素集合，通常用 $\Sigma$ 表示。符号集中的元素称为符号。
• 字符串（String）：在符号集 $\Sigma$ 中，任何由符号集中的符号组成的有限序列称为字符串。
• 空字符串（Empty String）：空字符串用 $\epsilon$
• 表示，长度为零，但仍是 $\Sigma$ 中的一个字符串。
• 所有可能的字符串集合（$\Sigma^*$）：$\Sigma^*$表示所有可能的字符串的集合，包括空字符串 $\epsilon$。

通过这些基本术语，可以更好地理解形式语言和自动机理论中的概念，这些概念在编译原理、模式匹配等领域中有广泛的应用。

Some examples

If x is a string of $∑$ and a∈ $∑$then xa/ax is a string of $∑$