编译原理学习-形式语言 乔姆斯基文法

四种文法

我觉得讲课的老师都不一定能搞清楚这些文法到底是什么东西

• 0型文法
• 1型文法
• 2型文法-上下文无关文法
• 3型文法

直接推出的严格定义

可以理解成字符串替换吧

有一个字符串αβγ
如果β→b是一个产生式，且α，γ∈（VT∪VN）*.
那么就可以有αβγ=>αbγ，叫做αβ直接推出αbγ.

推导的定义

α1=>α2=>α3=>...=>αn
叫做从α1到αn的一个推导，α1可以推导出αn

星号推出，加号推出。星号推出包含等于与加号推出