编译原理期末复习

参考资料：第3章 词法分析 丨正规文法构造状态转换图

9.根据确定有限自动机（DFA）写相应的右线性文法

一个确定的有穷自动机（DFA）M是一个五元组，即M=(K,VT,M,S,Z)

由有穷自动机构造右线性文法

令(FA)M=(K, V_T, M, S, Z)，则G=(V_N，V_T，P，S)

VN=K, VT= VT,S=S

P的确定方法如下：

若M(A，a)=B，则将产生式A→aB加到P；(包括B∈Z和B不∈Z两种情况)

若M(A, a)=B，且B∈Z，则将产生式A→ a加到P；

若S也是一个终态，则将产生式S →ε加到P。