什么是上下文无关文法？举例说明

上下文无关文法 (CFG) 是一种形式文法，用于生成给定形式语言中所有可能的字符串模式。

它被定义为四个元组 -

G=(V,T,P,S)

• G 是一个文法，它包含一组产生式规则。它用于生成语言的字符串。
• T 是终结符的集合。它用小写字母表示。
• V 是非终结符的集合。它用大写字母表示
• P 是一组产生式规则，用于将字符串中的非终结符（产生式左侧）替换为其他终结符（产生式右侧）。
• S 是用于推导出字符串的起始符号

示例

为在集合∑={a} 上具有任意数量 a 的语言构建 CFG

解决方案

正则表达式= a*

正则表达式的产生式规则如下 -

S->aS 规则 1

S-> ε 规则 2

现在，如果我们想推导出字符串“aaaaaa”，我们可以从起始符号开始

从起始符号开始

正则表达式=a* 可以生成一组字符串 { ε,a,aa,aaa,...}

我们可以有一个空字符串，因为 S 是起始符号，规则 2 给出 S-> ε

Bhanu Priya

更新于: 2021年6月11日

45K+ 浏览量

启动你的 职业生涯

通过完成课程获得认证

开始学习