3型文法(正规文法,包括右线性文法和左线性文法):对应的自动机是有限自动机(包括确定的有限自动机DFA和非确定的有限自动机NFA)
首先回顾Chomsky文法体系与自动机的对应关系:
Chomsky文法分为0型、1型、2型、3型文法。0型文法(无限制文法):对应的自动机是图灵机。0型文法的产生式形式为(\alpha\rightarrow\beta),其中(\alpha\in(V_N\cup V_T)^)且…
2026/7/21 8:01:57