状态转换图与文法雅导 用状态转换图识别符号串w的过程，就是为w建立一个 推导S→*w的过程。 在第一步（在初始状态S下，扫描到a而过渡到下一状 态A)，由状态转换图的构造规则可知，G中必有产 生式S→aA;对于识别过程的后续步骤，由状态A识别 a+1后过渡到A恰好对应了使用产生式A→a+1A,, 最后在状态Aa-识别a后到达终态F,对应了使用产生 式 A→a进行推导： ·S→aA1→a1a2A2→…→a1a2…an-1An-1 →a1a2.an 状态转换图与文法推导 • 用状态转换图识别符号串w的过程，就是为w建立一个 推导S* w的过程。 • 在第一步（在初始状态S下，扫描到a1而过渡到下一状 态A1），由状态转换图的构造规则可知，G中必有产 生式S→a1A1;对于识别过程的后续步骤，由状态Ai识别 ai+1后过渡到Ai+1恰好对应了使用产生式Ai →ai+1Ai+1,…, 最后在状态An-1识别an后到达终态F，对应了使用产生 式 A →an进行推导： • S a 1A1a 1a 2A2…… a 1a2…an-1An-1 a 1a2…an