10 关系: 上下文有关语言,形式语言,形式文法,嵌入下推自动机,解析,自然语言,附标语言,附标文法,树-邻接文法,泵引理。
上下文有关语言
在理论计算机科学中,上下文有关语言是可被上下文有关文法定义的形式语言。它是乔姆斯基层级中的四类文法之一。当然它在理论和实践中都是最少使用的。.
新!!: 适度上下文有关语言和上下文有关语言 · 查看更多 »
形式语言
在数学、逻辑和计算机科学中,形式语言(Formal language)是用精确的数学或机器可处理的公式定义的语言。 如语言学中语言一样,形式语言一般有两个方面: 语法和语义。专门研究语言的语法的数学和计算机科学分支叫做形式语言理论,它只研究语言的语法而不致力于它的语义。在形式语言理论中,形式语言是一个字母表上的某些有限长字符串的集合。一个形式语言可以包含无限多个字符串。.
新!!: 适度上下文有关语言和形式语言 · 查看更多 »
形式文法
在计算机科学中,形式语言是:某个字母表上,一些有限长字串的集合,而形式文法是描述这个集合的一种方法。形式文法之所以这样命名,是因为它与人类自然语言中的文法相似的缘故。 形式文法描述形式语言的基本想法是,从一个特殊的初始符号出发,不断的应用一些产生式规则,从而生成出一个字串的集合。产生式规则指定了某些符号组合如何被另外一些符号组合替换。举例来说,假设字母表只包含'a'和'b'两个字符,初始符号是'S',我们应用下述规则: 于是我们可以通过把"S"重写为"aSb"(规则1),我们还可以继续应用这条规则把"aSb"重写为"aaSbb"。这个重写的过程不断重复,直到结果中只包含字母表中的字母为止。在例子中,我们可以得到S -> aSb -> aaSbb -> aababb这样的结果。由文法刻画的语言,包含了所有可以这样产生的字串,比如ba, abab, aababb, aaababbb等等。.
新!!: 适度上下文有关语言和形式文法 · 查看更多 »
嵌入下推自动机
嵌入下推自动机或 EPDA 是分析树-邻接文法(TAG)的计算模型。除了不再使用堆栈来存储符号之外,它类似于分析上下文无关文法的下推自动机。它有存储符号的重复堆栈组成的一个栈,这给予了 TAG 在上下文无关文法和上下文有关文法之间的复杂度,或者说是适度上下文有关文法的子集。.
新!!: 适度上下文有关语言和嵌入下推自动机 · 查看更多 »
解析
解析可以指:.
新!!: 适度上下文有关语言和解析 · 查看更多 »
自然语言
自然语言(Natural language)通常是指一种自然地随文化演化的语言。英语、汉语、法語、西班牙語、日语为自然语言的例子,而世界语则为人工语言,即是一种由人特意为某些特定目的而创造的语言。 不过,有时所有人类使用的语言(包括上述自然地随文化演化的语言,以及人工语言)都会被视为“自然”语言,以相对于如编程语言等为计算机而设的“人造”语言。这一种用法可见于自然语言处理一词中。自然语言是人类交流和思维的主要工具。.
新!!: 适度上下文有关语言和自然语言 · 查看更多 »
附标语言
标语言是 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)文法在某种意义上类似于上下文无关文法,但是基本的重写单位是树而不是符号。上下文无关文法有把符号重写为其他符号的规则,而树-毗连文法有把树的节点重写为其他树的规则。.
新!!: 适度上下文有关语言和树-邻接文法 · 查看更多 »
泵引理
在可计算性理论中的形式语言理论中,泵引理声称给定类的任何语言可以被“抽吸”并仍属于这个类。一个语言可以被抽吸,如果在这个语言中任何足够长的字符串可以分解成片段,其中某些可以任意重复来生成语言中更长的字符串。这些引理的证明典型的需要计数论证比如鸽笼原理。 两个最重要例子是正则语言的泵引理和上下文无关语言的泵引理。鄂登引理是另一种更强的上下文无关语言的泵引理。 这些引理可以用来确定特定语言不在给定语言类中。但是它们不能被用来确定一个语言在给定类中,因为满足引理是类成员关系的必要条件,但不是充分条件。 泵引理是1961年由 Y. Bar-Hillel、M. Perles 和 E. Shamir首次发表的。.
新!!: 适度上下文有关语言和泵引理 · 查看更多 »