摘要：构造接收复杂语言的自动机是困难的，而复杂语言可以通过简单的语言进行语言间的运算而得到，文章根据右线性语言、上下文无关语言和上下文相关语言对联合，连接和迭代运算是封闭的特点，提出了利用简单自动机构造复杂自动机的方法。
 
    关键词：语言；语言的运算；语言运算的封闭性；有限状态自动机；下推自动机
 
    在形式语言和自动机的理论中，构造自动机识别和接收一个语言是研究的重点。对于复杂的语言，直接构造对应的自动机容易造成不一致性。如果一个语言是由3种基本运算中的某一种运算得到的，可以将该语言分解为比较简单的语言，先构造出接收简单语言的自动机，再利用语言运算的封闭性原理，就可以根据简单自动机直接构造出复杂自动机。
 
    一、构造下推自动机
 
    若语言l1和l2是两个上下文无关语言，分别接收语言l1和l2的下推自动机为：
 
    m1=（q1，∑1，Γ1，δ1，q1，z01，Φ）
 
    m2=（q2，∑2，Γ2，δ2，q2，z02，Φ）
 
    假设q1和q2相交，Γ1和Γ2不相交；下推自动机以空栈方式接收语言。
 
    （一）利用联合运算得到的语言构造
 
    pdam=（q1uq2u{q0}，∑1u∑2，Γ1uΓ2uz0，δ，q0，z0，Φ）
 
    其中δ函数为：δ（q0，ε，z0）=（q0，z01）δ（q0，ε，z0）=（q2，z02）。对于q1，中所有的状态q，Σ1u{ε}中的α，δ（q，α，z）=δ1（q，α，z）；对于q2中所有的状态q，Σ2u{ε}中的α，δ（q，α，z）=δ2（q，α，z）。
 
    该pdam包括了原来m1和m2的所有δ函数，增加了2个扫描ε的δ函数，使得：从pdam的开始状态出发，通过两个ε动作：δ（q0，ε，z0）=（q0，z01）和δ（q0，ε，z0）=（q2，z02），可以选择到达m1和m2的开始状态q1或q2，并将栈底符号z0改为m1和m2原来栈底符号z01或z02，然后使用m1和m2的自己的δ函数，到达m1和m2的接收格局（空栈）。显然pdam接收的语言是l（m1）和l（m2）的联合。
 
    （二）利用连接运算得到的语言构造
 
    pdam=（q1uq2u{q0}，∑1u∑2，Γ1uΓ2uz0，δ，q1，z01，Φ）
 
    其中δ函数为：对于q1中所有的状态q，Σ1u{ε}中的α，δ（q，ε，z）=δ1（q，ε，z）。对于m1最后的状态转换函数：δ1（q，α，z01）=（q’，ε）。增加：δ（q，α，z01）=（q2，z02）对于q2中所有的状态q，Σ2u{ε}中的b，δ（q，b，z）=δ2（q，b，z）。
 
    该pdam包括了原来m1和m2的所有δ函数，增加了1个δ函数，使得：从m1的开始状态q1出发，使得从m1自己的δ函数，接受了语言l1的串后，使得改造的函数δ（q，ε，z01）=（q2，z02），到达m2的开始状态q2，栈底变为m2的栈底z02，然后使用m2的自己的δ函数，借接收语言l2的串。显然pdam接收的语言是l（m1）和l（m2）的连接。
 
    （三）利用迭代运算得到的语言构造
 
    pdam=（q1uq2，∑1u∑2，Γ1uΓ2uz0，δ，q1，z01，Φ）
 
    其中δ函数为：δ（q1，α，z01）=（q1，ε）。对于q1中所有的状态q，Σ1u{ε}中的α，δ（q，α，z）=δ1（q，α，z）。对于m1最后的状态转换函数：δ1（q，ε，z01）=（q’，ε）。增加：δ（q，ε，z01）=（q2，z01）。
 
    该pdam包括了原来m1和m2的所有δ函数，增加了2个δ函数，使得：从m1的开始状态q1出发，使得新加的δ（q1，ε，z01）=（q1，ε），以便接收空串ε，或者使用m1自己的δ函数接收了语言l1的某个串后，以将栈置空，或者使用新加的函数δ（q，ε，z01）=（q，z01），重新到达m1的开始状态q1，栈底还是m1的栈底z01，以便迭代地接收输入串。显然pdam接收的语言是l（m1）的闭包。
 
    二、编写一个识别浮点数的自动机
 
    编写一个词法分析器：根据需要写出正规定义；根据正规定义画出转换图；根据转换图写出词法分析器。本文详细讨论面向过程的语言来实现一个词法分析器（如c语言）。
 
    我们需要一个nextchar（）函数，取得缓存中下一个等待分析的字符，这个函数完成2个任务：让输入指针向前移动一位；返回输入指针指向的字符。
 
    定义一个变量token_beginning，在每个状态转换图开始的时候，记录输入指针的位置，定义forward变量作为输入指针
 
    状态转换图被实现成为代码之后，每个状态都有属于自己的一块代码，这些代码按顺序完成以下工作：读取一个字符，通过nextchar（）函数。读取的字符（标志），如果它和当前状态的边上的标记相同，那么状态将转换到边所指向的状态，具体实现只需要一个语句就是state=xxx（xxx为目标状态）；如果当前状态的所有边的标记和这个读取字符不一样，那么表示没有找到token（词法记号），这时候需要调用fail（）函数。
 
    fail（）函数完成这样的功能：指针回移，完成forward＝token_beginning的操作。找到适当的开始状态。假定所有的转换图都被尝试过并且无法匹配，此时会调用一个发现错误的小程序来报告错误。