网站首页  情感咨询  情感美文  情感百科  情感生活  学习充电  旧版美文

请输入您要查询的词汇:

 

词汇 Chomsky normal form
分类 英语词汇 英语翻译词典
释义

Chomsky normal form

中文百科

乔姆斯基范式

在计算机科学中,一个形式文法是 Chomsky 范式的,当且仅当所有产生规则都有如下形式:

这里的 A, BC 是非终结符,α 是终结符(表示常量值的符号),S 是开始符号,而 ε 是空串。还有,BC 都不可以是开始符号。

所有的 Chomsky 范式的文法都是上下文无关,反过来,所有上下文无关文法都可以有效的变换成等价的 Chomsky 范式的文法。

除了(在文法可能生成空串的时候包括的)可选规则 S → ε 是例外,Chomsky 范式的文法的所有规则都是扩张的,就是说在字符串的整个导出过程中,每个终结符和非终结符的字符串比起前面导出的字符串要幺同样长度要幺多出一个元素。长度 n 的字符串的导出总是精确的 2n-1 步长。

英语百科

Chomsky normal form 乔姆斯基范式

Abstract syntax tree of the arithmetic expression

In formal language theory, a context-free grammar G is said to be in Chomsky normal form (first described by Noam Chomsky) if all of its production rules are of the form:

where A, B, and C are nonterminal symbols, a is a terminal symbol (a symbol that represents a constant value), S is the start symbol, and ε denotes the empty string. Also, neither B nor C may be the start symbol, and the third production rule can only appear if ε is in L(G), namely, the language produced by the context-free grammar G.

随便看

 

依恋情感网英汉例句词典收录3870147条英语例句词条,基本涵盖了全部常用英语单词的释义及例句,是英语学习的有利工具。

 

Copyright © 2004-2024 Yiyi18.com All Rights Reserved
京ICP备2021023879号 更新时间:2025/8/6 2:08:48