网站首页  英汉词典

请输入您要查询的英文单词:

 

单词 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.

随便看

 

英汉网英语在线翻译词典收录了3779314条英语词汇在线翻译词条,基本涵盖了全部常用英语词汇的中英文双语翻译及用法,是英语学习的有利工具。

 

Copyright © 2004-2024 encnc.com All Rights Reserved
更新时间:2025/6/18 7:55:42