迈希尔-尼罗德定理
在形式语言理论中，Myhill–Nerode 定理提供了一个语言是正则语言的必要和充分条件。它近乎专门的被用来证明一个给定语言不是正则的。 这个定理得名于 和 ，他们于1958年在芝加哥大学证明了这个定理。 定理陈述 给定一个字母集 (alphabet) \Sigma 以及其生成的语言 (language) L\subseteq\Sigma^，我們先來定義兩個字串 x, y\in\Sigma^ 之間彼此的關係：如果對於所有的後接字串 z…
标签：#形式语言
共 64 篇文章
Diff
diff是在UNIX系統上的一個工具程式，它可以比較兩個檔案之間的不同。通常它被用來比較同一個檔案，在不同版本間的差異。它可以產生一個副檔名為.diff或.patch的檔案，這個檔案可以被另一個工具程式patch來使用。 歷史及版本 這個程式最早是由貝爾實驗室所研發，1974年，由道格拉斯·麥克羅伊寫作的第五版，成為第一個正式版本。 參見 * 考異：歷史學中，考查古籍不同版本間的差異
Iota和Jot
在形式语言理论和计算机科学中，Iota（ι，发音如希腊字母 iota）和Jot（י，发音如希伯来字母 yodh）是两种极简的形式系统与编程语言。 这两个名称分别取自希腊语字母Ι（iota）和希伯来语字母Yodh（י/yodh）——分别是各自字母表中最小、最简单的字母，这一命名恰如其分地体现了这些语言的极简主义设计哲学。 它们的设计目标是比λ演算以及SKI组合子演算等更为人熟知的图灵完备系统更加简洁、更加基础。 因此，它们也被归类为图灵焦…
克莱尼星号
Kleene 星号，或稱Kleene 闭包，德语稱 Kleensche Hülle，在數學上是一種適用於字符串或符號及字元的集合的一元運算。當 Kleene 星号被應用在一個集合V時，寫法是V^。它被廣泛用於正则表达式。 定義及標記法 假定 : V_0=\{\epsilon\}\, 递归的定义集合 : V_{i+1}=\{wv : w\in V_i \wedge v \in V\}\, 这里的 i \geq 0\, 如果 V 是一个形式…
上下文无关文法
上下文无关文法（，縮寫為CFG），在计算机科学中，若一个形式文法 G = (V, Σ, P, S) 的产生式规则都取如下的形式：A -> α，則謂之。其中 A∈V ，α∈(V∪Σ) 。上下文无关文法取名为“上下文无关”的原因就是因为字符 A 总可以被字串 α 自由替换，而无需考虑字符 A 出现的上下文。如果一个形式语言是由上下文无关文法生成的，那么可以说这个形式语言是上下文无关的。（条目上下文无关语言）。 上下文无关文法重要的原因在于它…
最近字符串
在理论计算机科学中，最近字符串试图找到一组输入字符串的几何中心，是一个NP 难的计算问题 ， 要理解字符串的“中心”，就必须先定义两个字符串之间的距离。通常，该问题下的距离是指汉明距离。 正式定义 更正式地说，给定n 个长度为 m 的字符串 s_1, s_2, ..., s_n，最近字符串问题旨在寻找一个长度为m 的新字符串s，使得\max_{i=1, 2, , ..., n} d(s, s_i) = k 尽可能小，其中d是汉明距离。 …
字母表 (计算机科学)
在计算机科学中，字母表是字符或数字的有限集合。最常见的字母表是二元字母表{0,1}。有限字符串是来自字母表的字符的有限序列；例如二元字符串是来自字母表{0,1}的字符构成的字符串。字符的无限序列也可以用来自一个字母表的元素来构造。 给定一个字母表\Sigma，我们写\Sigma^来指示在字母表\Sigma上的所有有限字符串的集合。这里的{}^指示Kleene星号算子。我们写\Sigma^\infty(偶尔\Sigma^\N或\Sigma…
正则表达式
正则表达式（，常简写为、或），又称規律表達式、正規-{zh-cn:表示式; zh-tw:表達式; zh-hk:表示式;}-、正規表示法、規則運算式、常規表示法，是计算机科学概念，用簡單字串来描述、匹配文中全部符合指定格式的字串，現在很多文本编辑器都支援用正則表达式搜尋、取代符合指定格式的字串。 许多程序设计语言都支援用正則表达式操作字串，如Perl就内建功能强大的正則表达式引擎。正則表达式这概念最初由Unix的工具软件（例如sed和gr…
SCIgen
SCIgen是一个计算机程序，能够自动生成无意义的英文计算机科学研究论文，并且包含图片、表格、流程图和参考文献等。这个程序使用用户定制的上下文无关文法来生成论文的各类组成元素。 简介 SCIgen由美国麻省理工学院计算机科学与人工智能实验室的三位研究生杰里米·斯特里布林（Jeremy Stribling）、马克斯·克伦（Max Krohn）和达纳·阿瓜约（Dan Aguayo）编写，源代码以GPL协议发布。 影响 2005年，SCIge…
形式文法
在形式语言理论中，文法（formal grammar)是形式语言中字符串的一套产生式规则（production rule）。这些规则描述了如何用语言的字母表生成符合句法(syntax)的有效的字符串。文法不描述字符串的含义，也不描述在任何上下文中可以用它们做什么——只描述它们的形式。 形式语言理论是应用数学的一个分支，是研究形式文法和语言的学科。它在理論計算機科學、理论语言学、形式语义学、数理逻辑等领域有着广泛的应用。 形式文法是从一个…
附标语言
附标语言是 Alfred Aho 发现的一类形式语言 ；它们用附标文法描述并由嵌套堆栈自动机识别 。 附标语言是上下文有关语言的真子集和适度上下文有关语言和上下文无关语言的真子集；它们在并集、串接(concatenation)和Kleene星号下闭合，但在交集和补集下不闭合。Gerald Gazdar 已经依据线性附标语法特征化了适度上下文有关语言。 附标语言在自然语言处理中作为上下文无关语言的计算可承受的一般化有着实践重要性，因为附标…
附标文法
附标文法是描述附标语言的形式文法。它们有三个无交集的符号集合: 普通终结符、非终结符和只出现在中间推导中的附标(index)的集合。产生式可以如上下文无关文法那样把一个非终结符替代为终结符和非终结符的字符串，但是它还把非终结符替代为跟随着一个附标的非终结符，把跟随着一个附标的非终结符替代为非终结符。 附标只可以出现在非终结符之后或其他附标之后，所以所有非终结符都可以被看作跟随它之后的这些附标的所有者，它们形成了一个栈(产生式在非终结符之…
蒙塔古語法
蒙塔古文法（），又譯為蒙太古文法、蒙太格文法，由美國邏輯學家理查德·蒙塔古提出，用來研究自然語言語義學。他認為自然語言與形式語言在基本文法邏輯上是一致的，於1970年至1973年間提出一系列論文，形成蒙塔古文法，可用於自然語言處理。
合式公式
在形式系統與逻辑中，合式公式（well-formed formula，wff）又称合適公式、良式公式，可简称公式（formula），即“符合語法規則的公式”，是一逻辑体系中的“一个表达式”或“一个有限符号序列”；此表达式或序列，来自给定的字母表（字符），且属于形式语言的一种。合式公式与该逻辑体系的构成规则相符合，类似于自然语言中的一个语法句子。 若给定一形式文法，则WFF是这个文法生成的任何字符串。 例如，在命题演算中符号序列((\al…
形式语言
在数学、逻辑和计算机科学中，形式语言（）是用精确的数学或机器可处理的公式定义的语言。 如语言学中语言一样，形式语言一般有两个方面：语法和语义。专门研究语言的语法的数学和计算机科学分支叫做形式语言理论，它只研究语言的语法而不致力于它的语义。在形式语言理论中，形式语言是一个字母表上的某些有限长字符串的集合。一个形式语言可以包含无限多个字符串。 语言的形式定义 字母表与字符串 语言定义在某一个特定的字母表上，字母表（经常记作 Σ ）可以为任意…
克莱尼代数
克莱尼代数（名稱源自于美国数学家逻辑学家 斯蒂芬·科尔·克莱尼）在数学中是下列两个事物之一: 带有满足德·摩根定律和不等式 x∧−x ≤ y∨−y 的对合(补)运算的有界分配格。所以所有布尔代数都是 Kleene 代数，但是多数 Kleene 代数不是布尔代数。如同布尔代数有关于经典命题逻辑，Kleene代数有关于Kleene的三值逻辑。 推广来源自正则表达式的运算的代数结构。本文余下部分采用这种Kleene代数的概念。 定义 在文献中…
确定有限状态自动机
在计算理论中，确定有限状态自动机或确定有限自动机（）是一个能实现状态转移的自动机。对于一个给定的属于该自动机的状态和一个属于该自动机字母表\Sigma的字符，它都能根据事先给定的转移函数转移到下一个状态（这个状态可以是先前那个状态）。 基础概念 定义 确定有限状态自动机\mathcal{A}是由 一个非空有限的状态集合Q 一个输入字母表\Sigma（非空有限的字符集合） 一个转移函数\delta: Q \times \Sigma \ra…
两级文法
两级文法是下列两种形式结构之一： 两级形式语言的形式文法，这种语言是按两个级别来指定的形式语言，比如，字和句两个级别。 用来生成其他形式文法的形式文法[https://web.cs.wpi.edu/~jshutt/adapt/2level.html]。定义次级文法的规则的上下文无关文法可以生成导出文法的规则的一个有效的无限集合。可以生成另一个上下文无关文法的两级文法比单一层上下文无关文法更加强力，因为有生成力的两级文法已经实际上被证实是…
L系統
Lindenmayer系統，簡稱L系統，是由荷兰烏特勒支大學的生物学和植物学家，匈牙利裔的阿里斯蒂德·林登麦伊尔（Aristid Lindenmayer）於1968年提出的有关生长发展中的细胞交互作用的数学模型，尤其被廣泛應用於植物生長過程的研究。 L-system是一系列不同形式的正规语法规则，多被用于植物生长过程建模，但是也被用于模拟各种生物体的形态。L-system也能用于生成自相似的分形，例如迭代函数系统。 起源 作为一位生物学…
随机上下文无关文法
随機上下文无关文法（）即在上下文无关文法中，为每一个产生式规则赋予一个概率，标示应用一个产生式规则的可能性。 参见 上下文有关文法 形式文法 * 分析表达式文法