数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学编译器设计中的乔姆斯基层次结构是什么？
乔姆斯基层次结构是一组不同的形式语法。使用这种形式语法，可以生成一些形式语言。它们可以通过多种类型的设备来定义，这些设备可以识别这些语言，例如有限状态自动机、下推自动机、线性有界自动机和图灵机。
乔姆斯基提出了四种不同的短语结构语法类别，如下所示：
0型文法（无限制文法） - 0型文法对替换规则没有任何限制。左边的字符串中必须出现非终结符。生成的语言称为递归可枚举语言。
因此，0型文法是：
一个终结符字母表∑。
一个包含起始符号的非终结符字母表∀。$\sum\cup V,′α′$包含至少一个非终结符，并且对′β′没有限制。0型文法由图灵机识别。让我们考虑一个例子，文法G可以表示为：
G=(V,T,P,S)
V=set of non−terminals={A,B,C}
T=set of terminals={a}
S=start symbol={A}产生式P如下所示：
A→AB
AB→BC
B→α
1型文法（上下文有关文法） - 如果文法满足以下条件，则该文法被称为1型文法或上下文有关文法：
每个产生式都形如α→β，并且α的长度小于或等于β的长度，即没有空产生式，其中右侧是空字符串∈。
每个产生式都形如α1Aα2→ α1 βα2，其中$β≠∈$。可以构造图灵机来识别由上下文有关文法 (CSG) 生成的上下文有关语言。假设文法 G (V, T, P, S) 是上下文有关语言的一个例子，其中
V={A,B,C}
T={a,b}
S={A}
产生式由下式给出：
A→AB
AB→BC
C→ab
2型文法（上下文无关文法） - 如果产生式形如 A→α，其中 A 是非终结符，而 α 是一个语义形式，即 α ∈ (V ∪T)∗，即 α 可以是 ∈，则该文法被称为上下文无关文法/2型文法。产生式的左侧必须只包含一个非终结符。
2型文法可以用下推自动机识别。假设文法 G(V,T,P,S)=({S},{a,b},P,S)，其中 P 包含 S→aSa|bSb|a|b 是上下文无关文法的例子。
3型文法（正则文法） - 如果产生式形如 A→a 或 A→aB，即每个产生式的左侧只应包含一个非终结符，或者右侧的第一个符号必须是终结符，并且可以后跟一个非终结符，则该文法被称为3型文法。
由该文法生成的语言由有限状态机识别。这些正则语言也可以用更简单的表达式来表示，称为正则表达式。
2K+ 次浏览
