数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究如何为上下文无关文法生成语言？
问题
为给定的上下文无关文法生成语言。
S->0S, S-> λ
S-> A0, A->1A, A-> λ
S->000S, S-> λ
解决方案
上下文无关文法 (CFG) 是一种形式文法，用于生成给定形式语言中所有可能的字符串模式。
CFG 由四个元组定义
G=(V,T,P,S)
其中，
- T：终结符集（小写字母）符号。
- V：顶点或非终结符（大写字母）。
- P：产生式规则。
- S：开始符号。
示例 1
语法为：
S->0S, S->λ
情况 1 - S->0S
->0
情况 2 - S->0S
->00S
->00
情况 3 - S->0S
->00S
->000S
->000
因此，为给定语法生成的语言为：
L={e,0,00,000……..}
示例 2
语法为：
S-> A0, A->1A, A-> λ
情况 1 - S->A0
->0
情况 2 - S->A0
->1A0 {A->1A}
->10
情况 3 - S->A0
->1A0
-> 11A0
->110
因此，基于给定语法的生成语言为：
L={0,10,110,…………….}
示例 3
语法为：
S->000S, S-> λ
情况 1 - S->000S
->000
情况 2 - S->000S
->000000S
->000000
因此，基于给定语法的生成语言为：
L={ ε,000,000000,……….}
更新于： 2021年6月12日
4K+ 次查看
广告