转换为乔姆斯基范式 [英] Conversion to Chomsky Normal Form
问题描述
我确实需要您的帮助. 我有这些作品:
I do need your help. I have these productions:
1) A--> aAb
2) A--> bAa
3) A--> ε
我应该应用乔姆斯基范式(CNF).
I should apply the Chomsky Normal Form (CNF).
为了应用上述规则,我应该:
In order to apply the above rule I should:
- 消除ε生产
- 消除单一生产
- 删除无用的符号
我立即陷入困境.原因是A是可为空的符号(ε是其主体的一部分)
Immediately I get stuck. The reason is that A is a nullable symbol (ε is part of its body)
我当然不能删除A符号.
Of course I can't remove the A symbol.
有人可以帮助我获得最终解决方案吗?
Can anyone help me to get the final solution?
推荐答案
要开始转换为Chomsky范式(使用Wikipedia页面提供的定义(1)),您需要找到一个等效的,本质上是非合同的语法.开头为S
的语法G
本质上是无约束的iff
To begin conversion to Chomsky normal form (using Definition (1) provided by the Wikipedia page), you need to find an equivalent essentially noncontracting grammar. A grammar G
with start symbol S
is essentially noncontracting iff
1. S is not a recursive variable
2. G has no ε-rules other than S -> ε if ε ∈ L(G)
调用语法G
时,具有非递归开始符号的等效语法G'
为:
Calling your grammar G
, an equivalent grammar G'
with a non-recursive start symbol is:
G' : S -> A
A -> aAb | bAa | ε
很显然,G'
的可为空的变量集是{S,A}
,因为A -> ε
是G'
的生成,而S -> A
是链规则.我假设您已获得一种从语法中删除ε规则的算法.该算法应产生类似于以下内容的语法:
Clearly, the set of nullable variables of G'
is {S,A}
, since A -> ε
is a production in G'
and S -> A
is a chain rule. I assume that you have been given an algorithm for removing ε-rules from a grammar. That algorithm should produce a grammar similar to:
G'' : S -> A | ε
A -> aAb | bAa | ab | ba
语法G''
本质上是非契约的;您现在可以将其余算法应用于语法,以找到Chomsky范式的等效语法.
The grammar G''
is essentially noncontracting; you can now apply the remaining algorithms to the grammar to find an equivalent grammar in Chomsky normal form.
这篇关于转换为乔姆斯基范式的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!