数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究给出一些非正则的上下文无关语言的例子。
上下文无关文法 (CFG) 由一组有限的语法规则组成，是一个四元组 **(V, T, P, S)**
其中：
V 是变量（非终结符）。
T 是一组终结符。
P 是一组规则，P: V→ (V ∪ T)*，即产生式规则的左端。P 不具有任何右上下文或左上下文。
S 是起始符号。
使用任何语言的规则，我们可以推导出该语言中的任何字符串。
对于语言 a*，CFG 如下：
S -> aS
S -> ɛ
这里：
S 是变量。
a 和 ɛ 是终结符。
S 是起始符号。
使用这些规则，我们可以推导出任意数量的 a。
例如，考虑字符串 aaaaa 的 CFG 如下所示：
S aS rule 1 aaS rule 1 aaaS rule 1 aaaaS rule 1 aaaaaS rule 1 aaaaaɛ rule 2 aaaaa
上下文无关语言是由上下文无关文法创建的，它包含正则语言。
相同的上下文无关语言可以由多个上下文无关文法生成。
示例 1
一个非正则但属于上下文无关语言的例子是 **{ anbn | n >= 0 }**
上述例子包含所有 a 和 b 数量相等的字符串，符号 a3b3 可以扩展为 aaabbb，其中有三个 a 和三个 b。
抽吸引理 (Pumping Lemma) 提供了进行否定测试的能力。如果语言不满足抽吸引理，则可以说它不是上下文无关的。抽吸引理是一个数学证明，将其应用于上下文无关语言需要时间。
示例 2
考虑另一个非正则的上下文无关语言的例子。
S -> aSb | ɛ
这个例子不是正则的，因为我们无法用有限状态机或正则表达式来表达它。我们应该能够计算 A 的数量并检查 B 的数量是否匹配。此外，由于 n 可以是任何值，因此无法用有限状态机来完成。
更新于：2021年6月16日
2K+ 次浏览
广告