数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 TOC 中解释乔姆斯基层次结构
乔姆斯基层次结构表示不同机器接受的语言类别。
乔姆斯基层次结构
根据乔姆斯基的语法层次结构如下所述，根据语法类型：
类型 0 - 无限制语法
无限制语法 - 无限制语法是 4 元组 (T,N,P,S)，它包括：
T = 终结符集
N = 非终结符集
P = 产生式集，形式为：
v->w
其中 v 和 w 是由非终结符和终结符组成的字符串。
S = 称为起始符号。
示例 - 图灵机 (TM)
类型 1 - 上下文相关语法
所有产生式都具有以下形式：
v -> w 其中 |v| < |w|
uAv -> uwv 其中 w != epsilon，
即，A -> w，但仅在 u _ v 的上下文中。
上下文相关语法等价于线性有界和上下文相关语言。
示例 - 线性有界自动机 (LBA)
类型 3 - 上下文无关语法 -
所有产生式都具有以下形式：
A -> x - 其中 A 是非终结符，x 是非终结符和终结符的字符串，上下文无关语法等价于下推自动机 (PDA) 和上下文无关语言。
示例 - 下推自动机 (PDA)
类型 3 - 正则语法
所有产生式都具有以下形式：
A -> xB
A -> x 其中 A、B 是非终结符，x 是终结符字符串。
正则语法等价于正则集和有限自动机。
示例 - 有限自动机 (FA)
| 语法类型 | 语法接受 | 语言接受 | 自动机 |
|---|---|---|---|
| 类型 0 | 无限制语法 | 递归可枚举语言 | 图灵机 |
| 类型 1 | 上下文相关语法 | 上下文相关语言 | 线性有界自动机 |
| 类型 2 | 上下文无关语法 | 上下文无关语言 | 下推自动机 |
| 类型 3 | 正则语法 | 正则语言 | 有限状态自动机 |
乔姆斯基层次结构如下图所示：
更新于：2021 年 6 月 16 日
11K+ 次观看
广告