半自动机
在数学和计算机科学中，半自动机或M-act是幺半群在集合上的乘法性运算。从代数结构的观点来看，它非常接近于群作用的概念。从计算机科学的观点来看，它是只有输入没有输出的自动机。从范畴论的观点来看，作用是如范畴上的函子般重要。 这个概念也叫做*S-集合、M-集合、M-操作数、S-系统、S-自动机、转移系统、算子幺半群、变换半群或转移幺半群。本文力图表现出它们表示的是同一个概念，尽管在使用中有各种概念和术语的变体。 变换半群 變換半群或變換幺…
标签：#形式语言
共 64 篇文章
自由么半群
在抽象代數裡，於一集合A上的自由幺半群是指一幺半群，其元素都是由A內零個或多個元素以串接之二元運算形成的有限序列(或字符串)。通常標記為A。其單位元為空字元串，標記為ε 或 λ。在A上的自由半群則指是A*內的子半群，其包含除了空字串外的所有元素。通常標記為A+。 更一般地，一抽象幺半群(半群)S被稱做是自由的，若其與某一集合上的自由幺半群(半群)同構。 如其名稱所述，自由幺半群(半群)為滿足定義了自由对象的泛性質的物件，在幺半群(半群)…
乔姆斯基谱系
乔姆斯基体系是计算机科学中刻画形式文法表达能力的一个分类谱系，是由语言学家诺姆·乔姆斯基于1956年提出的。它包括四个层次： 0-型文法（无限制文法或短语结构文法）包括所有的文法。该类型的文法能够产生所有可被图灵机识别的语言。可被图灵机识别的语言是指能够使图灵机停机的字串，这类语言又被称为递归可枚举语言。注意递归可枚举语言与递归语言的区别，后者是前者的一个真子集，是能够被一个总停机的图灵机判定的语言。 1-型文法（上下文相关文法）生成上…
終結符與非終結符
終結符和非終結符在電腦科學和語言學的领域是用來指定推導規則的元素。在某個形式語法之中，終結符和非終結符是兩個不交的集合。 終結符 終結符是一個形式語言的基本符號。就是說，它們能在一個形式語法的推導規則的輸入或輸出字符串存在，而且它們不能被分解成更小的單位。確切地說，一個語法的規則不能改變終結符。例如說，下面的語法有兩個規則： #x -> xa #x -> ax 在這種語法之中，a是一個終結符，因為沒有規則可以把a變成別的符號。不過，有兩…
泵引理
在可计算性理论中的形式语言理论中，泵引理（Pumping lemma）声称给定类的任何语言可以被“抽吸”并仍属于这个类。一个语言可以被抽吸，如果在这个语言中任何足够长的字符串可以分解成片段，其中某些可以任意重复来生成语言中更长的字符串。这些引理的证明典型的需要计数论证比如鸽笼原理。 两个最重要例子是正则语言的泵引理和上下文无关语言的泵引理。鄂登引理是另一种更强的上下文无关语言的泵引理。 这些引理可以用来确定特定语言不在给定语言类中。但是…
正则语言
正则语言又称-{zh-cn:正规语言; zh-tw:正則語言; zh-hk:正規語言;}-是满足下述相互等价的一组条件的一类形式语言： 可被确定有限状态自动机识别； 可被非确定有限状态自动机识别； 可被只读图灵机识别； 可用正则表达式描述； 可用正则文法生成。 可用前缀文法生成。 例子 所有的有限语言都是正则的。 字母表{a, b}上包含偶数个a的所有字串构成的语言是正则的。 字母表{a, b}上取若干个a后紧跟若干个b形式的所有字串构…
递归语言
在数学、逻辑和计算机科学中，递归语言或遞迴語言是也叫做可判定语言或图灵可判定语言的形式语言类型。所有递归语言的类经常被称为 R。这种语言类型在乔姆斯基层级中没有定义。 定义 递归语言有两种等价的主要定义: 递归语言是在形式语言的字母表上的所有可能的字的集合的递归子集。 设 S ⊆ Σ 是一个语言，M 是一台图灵机， 若对于任何字符串 ω ∈ Σ，有 ω ∈ S 当且仅当 M 接受 ω ω ∉ S 当且仅当 M 拒绝 ω 则称 M 判定语…
乔姆斯基范式
在计算机科学中，一个形式文法是 Chomsky 范式的，当且仅当所有产生规则都有如下形式： :A → BC 或 :A → α 或 :S → ε 这里的 A, B 和 C 是非终结符，α 是终结符（表示常量值的符号），S 是开始符号，而 ε 是空串。还有，B 和 C 都不可以是开始符号。 所有的 Chomsky 范式的文法都是上下文无关，反过来，所有上下文无关文法都可以有效的变换成等价的 Chomsky 范式的文法。 除了（在文法可能生成…
上下文无关语言
上下文无关语言是可以用上下文无关文法定义的形式语言。所有上下文无关语言的集合同一于下推自动机所接受的语言的集合。 例子 一个原型上下文无关语言是 L = \{a^nb^n:n\geq1\}，它是所有非空、偶数长度字符串的语言，字符串的整个前半部分都是 a，整个后半部分都是 b。L 由文法 S\to aSb ~|~ ab 生成，并被下推自动机 M=(\{q_0,q_1,q_f\}, \{a,b\}, \{a,z\}, \delta, q_…
语法幺半群
语法幺半群，即在数学中，形式语言 L 的 语法幺半群 M(L) 是可识别语言 L 的最小的幺半群。 语法商 给定幺半群 M 的子集 S\subset M，可以定义由 S 中元素的形式左逆或右逆组成的集合。它们叫做商，可以定义右商和左商，依赖于串接的是哪一端。S 与一个元素 m\in M 的右商是集合 :S/m=\{u\in M \;\vert\; um\in S \} 类似的，左商是 :m\setminus S=\{u\in M \;\…
汤普森构造法
汤普森构造法在计算机科学中是指一个能将正则表达式转化为一个与之等价的非确定有限状态自动机（NFA）的算法。算法得到的NFA可以在编程中用于匹配一个正则表达式，这也是正则表达式引擎实现的基本思路之一。 正则表达式和非确定有限状态自动机是形式语言的两种不同的抽象表达方式。在诸如文本编辑器的高级“查找和替换”以及许多编程语言中，人们都习惯使用正则表达式来表示字符串的匹配模式。然而，当计算机执行匹配程序时，NFA却是更加适合的一种格式。因此，汤…
鄂登引理
在形式语言理论中，Ogden引理提供了在上下文无关语言的泵引理上灵活性的扩展。 Ogden 引理声称如果语言 L 是上下文无关的，则存在某个数 p > 0 (这里的 p 可以是也可以不是抽吸长度)，使得对于 L 中任何长度至少 p 字符串 w，和“标记” p 或更多个 w 中的位置的所有方式，w 可以被写为 :w = uvxyz 带有字符串 u, v, x, y 和 z，使得 vy 有至少一个标记了的位置，vxy 有最多 p 个标记了的…
扩展巴科斯范式
扩展巴科斯-瑙尔范式（EBNF, Extended Backus–Naur Form）是表达作为描述计算机编程语言和形式语言的正规方式的上下文无关文法的元语法(metalanguage)符号表示法。它是基本巴科斯范式(BNF)元语法符号表示法的一种扩展。 它最初由尼克劳斯·维尔特开发，最常用的 EBNF 变体由标准，特别是 ISO-14977 所定义。 基本 扩展巴科斯范式是一种表达形式语言文法的代码，如由终结符即可视字符、数字、标点符…
确定上下文无关文法
在形式文法理论中，确定上下文无关文法(DCFG)是上下文无关文法的真子集。确定上下文无关文法是确定下推自动机可识别的文法。确定上下文无关语言是确定上下文无关文法所定义的形式语言。 它们在计算机科学领域中特别重要，因为这些文法可以有效的识别，而非确定上下文无关文法需要回溯或其他复杂的技术；非确定步骤的每次出现，栈都必须被复制并接着被传播(propagate)，消耗运行时间、内存或两者。在实践中，当你希望为非确定文法(比如用 YACC)建立…
递归可枚举语言
在数学、逻辑和计算机科学中，递归可枚举语言是也叫做部分可判定语言或图灵可识别语言的形式语言类型。它在形式语言的乔姆斯基层级中叫做类型-0语言。所有递归可枚举语言的类叫做RE。 形式定义 递归可枚举语言定义：设S ⊆ Σ为一个语言，E是一个枚举器，若L（E） = S，则称E 枚举了语言S。若存在这样 的E，S就称为递归可枚举语言。 注意，枚举器E可以以任意的顺序枚举语言L（E），而且L（E） 中的某个串可能会被E多次重复地打印。 图灵可识…
不收缩文法
形式定义 在形式语言理论中，文法是不收缩的（或单调的），如果所有它的产生规则都有如下形式 :α -> β 这里的 |α| ≤ |β|，|α| 指示 α 的长度。 就是说，没有规则会减少被重写的字符串的大小。 它是本质不收缩的，如果可有一个例外，也就是，规则 :S → ε 这里的 S 是开始符号而 ε 是空串。 例子 :S → abc :S → aSBc :cB → Bc :bB → bb 这个文法生成语言 \{ a^n b^n c^n …
格雷巴赫标准式
在计算机科学中，声称一个上下文无关文法是Greibach 标准式（范式）(GNF)的意味着所有的产生规则都有如下形式： :A \to \alpha X 或 :S \to \epsilon 这里的 A 是非终结符，α 是终结符，X 是不包括开始符号的非终结符的（可能为空）的序列，S 是开始符号，而 ε 是空串。 可观察出这种文法没有左递归。 所有上下文无关文法口可以被转换成等价的 Greibach 范式的文法。（某些定义不认可第二种形式的…
黑田范式
在计算机科学中，形式文法是 Kuroda 范式的，当且仅当所有产生规则都有如下形式: :AB → CD 或 :A → BC 或 :A → B 或 :A → α 这里的 A, B, C 和 D 是非终结符而 α 是终结符。 所有 Kuroda 范式的文法都是单调的，因此生成上下文有关语言。反过来说，所有不生成空串的上下文有关语言都可以被 Kuroda 范式的文法所生成。 参见 巴科斯范式 乔姆斯基范式 Greibach范式 上下文有关文法…
可识别语言
在数学和计算机科学中，可识别语言是可被有限状态机识别的形式语言。等价的说，可识别语言是语法关系的商的家族为有限的的形式语言。 定义 给定一个幺半群 M，在 M 上的语言简单的是子集 L\subset M。这样的语言被称为在 M 上可识别的，如果有在 M 上的有限状态机接受 L 作为输入。在 M 上的有限状态机简单的是以 M 的元素作为输入，接受或拒绝它们的有限自动机。 在 M 上的可识别语言的家族指示为 REC(M)。 例子 如果 M …
正则文法
在计算机科学中，正则文法是产生式规则取下述形式的一种形式文法（N, Σ, P, S）： A -> a ，此处的A是N中的非终结符号，a是Σ中的终结符号； A -> aB，此处的A和B是N中的非终结符号，a是Σ中的终结符号； C -> ε，此处的C是N中的非终结符号。 下面给出一个正则文法的例子： 文法G = (N, Σ, P, S)，其中N = {S, A}，Σ = {a, b, c}，S是起始符号，P包含下述规则： :S -> aS …