转换图的运行和接受 转换图在运行的时候,由一个当前的状 态。每次输入一个符号的时候,转换图 的状态改变如下:沿着从当前状态离开 的,并且用输入符号标记的边,到达这 个边的目标状态 一个符号串被状态转换图接受当且仅当 从初始状态出发,逐次输入符号串中的 所有符号的时候,最终的状态是接受状
转换图的运行和接受 • 转换图在运行的时候，由一个当前的状 态。每次输入一个符号的时候，转换图 的状态改变如下：沿着从当前状态离开 的，并且用输入符号标记的边，到达这 个边的目标状态。 • 一个符号串被状态转换图接受当且仅当 从初始状态出发，逐次输入符号串中的 所有符号的时候，最终的状态是接受状 态
从文法构造状态转换图 我们可以给每个正则文法构造一个状态 转换图。 其基本思想如下: 当我们使用自底向上的方式规约一个正则文 法的句子的时候,得到的句型都是形如 Utx(tx为终结符号串)。而下次规约的规则总 是满足V∴=Ut。如果我们把非终结符号作为 状态,而把饮看作尚未读入的部分时,就得 到一个状态转换图。P61图3-4
从文法构造状态转换图 • 我们可以给每个正则文法构造一个状态 转换图。 • 其基本思想如下： – 当我们使用自底向上的方式规约一个正则文 法的句子的时候，得到的句型都是形如 Utx(tx为终结符号串)。而下次规约的规则总 是满足V::=Ut。如果我们把非终结符号作为 状态，而把tx看作尚未读入的部分时，就得 到一个状态转换图。P61图3-4
从文法构造状态转换图(算法) 步骤一:引入一个开支状态S(假定S不 是非终结符号 步骤二:每个非终结符号作为一个结点。 步骤三 Q:=T:从S到Q有一条标记为T的弧 Q:=RT:从R到Q有一条标记为T的弧。 识别符号为接受状态
从文法构造状态转换图(算法) • 步骤一：引入一个开支状态S（假定S不 是非终结符号。 • 步骤二：每个非终结符号作为一个结点。 • 步骤三： – Q::=T：从S到Q有一条标记为T的弧。 – Q::=RT：从R到Q有一条标记为T的弧。 • 识别符号为接受状态
从文法构造状态转换图(例子) A Z: :Za Aa Bb A: : a S z B: =Ab b
从文法构造状态转换图(例子) S A B Z Z ::= Za | Aa | Bb A::= Ba | a B ::= Ab | b
使用状态转换图构造正则文法 从构造步骤来看,正则文法和状态转换 图之间具有一种对应关系 状态转换图具有直观的特点,所以给定 个正则语言,构造状态转化图比较方 便
使用状态转换图构造正则文法 • 从构造步骤来看，正则文法和状态转换 图之间具有一种对应关系。 • 状态转换图具有直观的特点，所以给定 一个正则语言，构造状态转化图比较方 便