布尔语法

布尔语法，由Okhotin提出，是形式语言理论中研究的一类形式语法。它们扩展了语法的基本类型–无语境语法，具有连接和否定的操作。除了这些明确的操作外，布尔语法还允许隐含的不连接，由单个非终端符号的多个规则表示，这是在无语境语法中xxx可以表达的逻辑连接。连接和否定尤其可以用来指定语言的相交和互补。一类中间的语法被称为连接性语法，允许连接和分离，但不允许否定。布尔语法的规则是这样的{displaystyleSigma}上的每一个字符串{displaystyleSigma}都满足所代表的每个语法条件。满足每个句法条件，由{displaystyle`alpha_{m}}并且没有一个句法条件是代表着的。所代表的句法条件中，没有一个是由{displaystyleβ_{1}}所代表的句法条件都没有。{displaystyleβ_{n}}因此满足定义的条件。

因此，满足以下定义的条件{displaystyleA}。存在几个关于布尔语法生成的语言的正式定义。它们有一个共同点：如果语法被表示为一个具有并集、交集、补集和联集的语言方程系统，那么语法生成的语言必须是这个系统的解。语义学在细节上有所不同，有的用语言方程定义语言，有的借鉴了逻辑编程领域的思想。然而，这些形式化定义的非微不足道的问题大多与实际考虑无关，人们可以根据给定的非正式语义来构造语法。该模型的实际属性与共轭语法的属性相似，而描述能力得到了进一步的提高。特别是保留了一些从无语境语法中继承的实际有用的属性，比如高效的解析算法，见Okhotin(2010)。