目录
17 关系: 上下文有关语言，上下文有关文法，乔姆斯基范式，形式语言，形式文法，嵌入下推自动机，计数器，诺姆·乔姆斯基，递归可枚举语言，递归语言，附标语言，附标文法，树-邻接文法，正则表达式，正则语言，正则文法，无限制文法。
上下文有关语言
在理论计算机科学中，上下文有关语言是可被上下文有关文法定义的形式语言。它是乔姆斯基层级中的四类文法之一。当然它在理论和实践中都是最少使用的。.
上下文有关文法
上下文有关文法(CSG，context-sensitive grammar)是一種形式文法，其中任何产生式规则的左手端和右手端都可以被终结符和非终结符構成的上下文所围绕。上下文有关文法比上下文无关文法更一般性，但仍足够有秩序得可以被线性有界自动机所解析。 上下文有关文法的概念是诺姆·乔姆斯基在1950年代介入的，被作为描述自然语言的语法的一种方式，在自然语言中一个单词是否可以出现在特定位置上，要依赖于上下文。可以被上下文有关文法描述的形式语言叫做上下文有关语言。.
乔姆斯基范式
在计算机科学中，一个形式文法是 Chomsky 范式的，当且仅当所有产生规则都有如下形式： 这里的 A, B 和 C 是非终结符，α 是终结符（表示常量值的符号），S 是开始符号，而 ε 是空串。还有，B 和 C 都不可以是开始符号。 所有的 Chomsky 范式的文法都是上下文无关，反过来，所有上下文无关文法都可以有效的变换成等价的 Chomsky 范式的文法。 除了（在文法可能生成空串的时候包括的）可选规则 S → ε 是例外，Chomsky 范式的文法的所有规则都是扩张的，就是说在字符串的整个导出过程中，每个终结符和非终结符的字符串比起前面导出的字符串要么同样长度要么多出一个元素。长度 n 的字符串的导出总是精确的 2n-1 步长。 Chomsky 范式得名于诺姆·乔姆斯基，他是发明乔姆斯基层级的美国语言学家。.
形式语言
在数学、逻辑和计算机科学中，形式语言（Formal language）是用精确的数学或机器可处理的公式定义的语言。 如语言学中语言一样，形式语言一般有两个方面: 语法和语义。专门研究语言的语法的数学和计算机科学分支叫做形式语言理论，它只研究语言的语法而不致力于它的语义。在形式语言理论中，形式语言是一个字母表上的某些有限长字符串的集合。一个形式语言可以包含无限多个字符串。.
查看 乔姆斯基谱系和形式语言
形式文法
在计算机科学中，形式语言是：某个字母表上，一些有限长字串的集合，而形式文法是描述这个集合的一种方法。形式文法之所以这样命名，是因为它与人类自然语言中的文法相似的缘故。 形式文法描述形式语言的基本想法是，从一个特殊的初始符号出发，不断的应用一些产生式规则，从而生成出一个字串的集合。产生式规则指定了某些符号组合如何被另外一些符号组合替换。举例来说，假设字母表只包含'a'和'b'两个字符，初始符号是'S'，我们应用下述规则： 于是我们可以通过把"S"重写为"aSb"（规则1），我们还可以继续应用这条规则把"aSb"重写为"aaSbb"。这个重写的过程不断重复，直到结果中只包含字母表中的字母为止。在例子中，我们可以得到S -> aSb -> aaSbb -> aababb这样的结果。由文法刻画的语言，包含了所有可以这样产生的字串，比如ba, abab, aababb, aaababbb等等。.
查看 乔姆斯基谱系和形式文法
嵌入下推自动机
嵌入下推自动机或 EPDA 是分析树-邻接文法(TAG)的计算模型。除了不再使用堆栈来存储符号之外，它类似于分析上下文无关文法的下推自动机。它有存储符号的重复堆栈组成的一个栈，这给予了 TAG 在上下文无关文法和上下文有关文法之间的复杂度，或者说是适度上下文有关文法的子集。.
计数器
在逻辑代数与電腦運算中，计数器是存储（有时还有显示）特定事件或过程发生次数的装置，往往与定時器訊號有关联。最常见的类型是有“时钟”输入线和多输出线的时序逻辑电路。输出线的值代表在二进制或BCD计数系统的数。每个施加到时钟输入的脉冲都会使计数器增加或是減少。 计数器电路通常由多个触发器级联连接而成。计数器在数字电路中使用非常广泛，會制成集成电路芯片以及作为更大集成电路的一部分。.
查看 乔姆斯基谱系和计数器
诺姆·乔姆斯基
艾弗拉姆·诺姆·乔姆斯基（Avram Noam Chomsky，），或譯作“荷姆斯基”，美國哲學家、語言學家、認知學家、邏輯學家、政治評論家。乔姆斯基是麻省理工学院语言学的荣誉退休教授，他的生成语法被认为是20世纪理论语言学研究上的重要贡献。他對伯尔赫斯·弗雷德里克·斯金纳所著《口語行为》的評論，也有助於发动心理学的认知革命，挑战1950年代研究人類行為和语言方式中占主导地位的行为主义。他所採用以自然為本來研究语言的方法也大大地影響了语言和心智的哲学研究。他的另一大成就是建立了乔姆斯基层级：根据文法生成力不同而对形式语言做的分类。乔姆斯基还因他对政治的热忱而著名，尤其是他对美国和其它国家政府的批评。從1960年評論越南戰爭以來，他的媒體和政治評論便越來越著名。一般认为他是活跃在美国政坛左派的主要知识分子。乔姆斯基把自己归为自由意志社會主義者，并且是无政府工团主义的同情者。据艺术和人文引文索引说，在1980年到1992年，乔姆斯基是被文献引用数最多的健在学者，并是有史以来被引用数第八多的學者。.
递归可枚举语言
在数学、逻辑和计算机科学中，递归可枚举语言是也叫做部分可判定语言或图灵可识别语言的形式语言类型。它在形式语言的乔姆斯基层级中叫做类型-0语言。所有递归可枚举语言的类叫做RE。.
递归语言
在数学、逻辑和计算机科学中，递归语言或遞迴語言是也叫做可判定语言或图灵可判定语言的形式语言类型。所有递归语言的类经常被称为 R。这种语言类型在乔姆斯基层级中没有定义。.
查看 乔姆斯基谱系和递归语言
附标语言
标语言是 Alfred Aho 发现的一类形式语言 ；它们用附标文法描述并由嵌套堆栈自动机识别 。 附标语言是上下文有关语言的真子集和适度上下文有关语言和上下文无关语言的真子集；它们在并集、串接(concatenation)和Kleene星号下闭合，但在交集和补集下不闭合。Gerald Gazdar 已经依据线性附标语法特征化了适度上下文有关语言。 附标语言在自然语言处理中作为上下文无关语言的计算可承受的一般化有着实践重要性，因为附标文法可以描述自然语言中出现的很多非局部约束。.
查看 乔姆斯基谱系和附标语言
附标文法
标文法是描述附标语言的形式文法。它们有三个无交集的符号集合: 普通终结符、非终结符和只出现在中间推导中的附标(index)的集合。产生式可以如上下文无关文法那样把一个非终结符替代为终结符和非终结符的字符串，但是它还把非终结符替代为跟随着一个附标的非终结符，把跟随着一个附标的非终结符替代为非终结符。 附标只可以出现在非终结符之后或其他附标之后，所以所有非终结符都可以被看作跟随它之后的这些附标的所有者，它们形成了一个栈(产生式在非终结符之后增加或去除附标)。 实际上，附标的栈可以计数并记住应用了和以何种次序应用了什么规则。例如，附标文法可以描述非上下无关语言: 通过如下规则(f 和 g 是附标): S\to aAfc A\to aAgc ~|~ B Bf\to b Bg\to bB 在中间增长的 g 的栈计数 A 已经被展开来增加一个 a 和一个 c 的次数 (n-1)；在结束时所有 g 变成终结符 b。 判定一个附标文法是否识别一个字符串是NP-完全的。.
查看 乔姆斯基谱系和附标文法
树-邻接文法
树-邻接文法(TAG)是 Aravind Joshi 定义的文法形式化。树-邻接（adjoining）文法在某种意义上类似于上下文无关文法，但是基本的重写单位是树而不是符号。上下文无关文法有把符号重写为其他符号的规则，而树-毗连文法有把树的节点重写为其他树的规则。.
正则表达式
正则表达式（Regular Expression，在代码中常简写为regex、regexp或RE），又称--、正規表示法、正規運算式、規則運算式、常規表示法，是计算机科学的一个概念。正则表达式使用单个字符串来描述、匹配一系列符合某个句法规则的字符串。在很多文本编辑器裡，正則表达式通常被用来检索、替换那些符合某个模式的文本。 许多程序设计语言都支持利用正則表达式进行字符串操作。例如，在Perl中就内建了一个功能强大的正則表达式引擎。正則表达式这个概念最初是由Unix中的工具软件（例如sed和grep）普及开的。正则表达式通常缩写成regex，单数有regexp、regex，复数有regexps、regexes、regexen。.
查看 乔姆斯基谱系和正则表达式
正则语言
正规语言又称正则语言是满足下述相互等价的一组条件的一类形式语言：.
查看 乔姆斯基谱系和正则语言
正则文法
在计算机科学中，正规文法是产生式规则取下述形式的一种形式文法（N, Σ, P, S）：.
查看 乔姆斯基谱系和正则文法
无限制文法
在形式语言理论中，无限制文法是对文法的产生式左右两侧都没有限制的形式文法。这是乔姆斯基层级中最一般性的文法类，它们可以识别任意的递归可枚举语言。.
查看 乔姆斯基谱系和无限制文法