自嵌入文法

自嵌入文法(self-embedding grammar)上下文無關文法的一種類型.如果在上下文無關文法中，存在著某一個非終極符號A，具有性質

這裡甲和滬是非空符號串，G表示上下文無關文法，=>表示推導關係，那么這個文法就是自嵌入文法.如果G是非自嵌入的上下文無關文法，那么由G生成的語言L(G)就是有限狀態語言.如果L(G)是上下文無關語言，那么若且唯若文法G是具有自嵌入性質的上下文無關文法時，L (G)才不是有限狀態語匹刁.