Chomsky谱系

设文法\(G=(V,T,\Gamma,S).\)约定变元用\(A,B,C,X,Y,Z\)等表示，终极符用\(a,b,c\)等表示，终极符串用\(x,y,z,u,v,w\)表示，变元和终极符串用\(\alpha,\beta,\gamma\)等表示。

0型文法：最一般的文法，无任何附加条件。对应0型语言(即r.e.语言)、一般Turning机。

1型文法：上下文有关文法CSG，对应上下文有关语言CSL、线性界限自动机LBA。每个产生式\(\alpha\to\beta\)都满足\(|\alpha|\ge |\beta|.\)

2型文法：上下文无关文法CFG，对应上下文无关语言CFL、下推自动机PDA。每个产生式形如\(A\to \alpha.\)

3型文法：正则文法，对应正则语言、有穷自动机FA。包括左线型文法和有限型文法两种，右线型文法的每个产生式形如\(A\to wB\)或\(A\to w.\)

    所属分类：TCS     发表于2021-12-05