数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学如何将CFG转换为格雷巴赫范式？
上下文无关文法 (CFG) 如果其产生式规则满足以下条件之一，则被称为格雷巴赫范式 (GNF)：
只有开始符号可以生成 ε。例如，如果 S 是开始符号，则 S → ε 属于 GNF。
非终结符可以生成终结符。例如，如果 A 是非终结符，a 是终结符，则 A → a 属于 GNF。
非终结符可以生成一个终结符，后跟任意数量的非终结符。例如，S → aAS 属于 GNF。
案例 1
G1 = {S → aAB | aB, A → aA| a, B → bB | b}
G1 的产生式规则满足 GNF 的规定规则，因此文法 G1 属于 GNF。
案例 2
G2 = {S → aAB | aB, A → aA | ε, B → bB | ε}
G2 的产生式规则不满足 GNF 的规定规则，因为：
A → ε 和 B → ε 包含 ε（只有开始符号才能生成 ε）。
因此，文法 G2 不属于 GNF。
将CFG转换为GNF的步骤
步骤 1 - 将文法转换为 Chomsky 范式 (CNF)。如果给定的文法不是 CNF，则将其转换为 CNF。
步骤 2 - 如果文法包含左递归，则消除它。如果上下文无关文法包含任何左递归，则消除它。
步骤 3 - 在文法中，将给定的产生式规则转换为 GNF 形式。如果文法中任何产生式规则不是 GNF 形式，则将其转换。
示例
考虑上下文无关文法
S→SS|(S)|a
将此文法转换为格雷巴赫范式。
解答
以下是将 CFG 转换为 GNF 的说明：
Step 1: Converting to CNF: S->SS|XSY|a X->( Y->) Step 2: Remove left recursion from S->SS S->XSYP/aP P->SP/ε X->( Y->) Step 3: Remove null production P->ε S->XSYP/aP P->SP/S X->( Y->) Step 4: Convert to GNF as S->XSYP is not in GNF, Replace X with ( S->(SYP/aP P->SP/S X->( Y->) Step 5: Convert to GNF as P->SP is not in GNF, Replace S with (SYP/aP S->(SYP/aP P->(SYPP/aPP/(SYP/aP X->( Y->)
更新于：2021年6月15日
15K+ 次浏览
广告