常规的语言
常规的语言
常规语言和有限自动机可以模拟需要非常少量内存的计算问题。例如,一个有限自动机可以生成一种规则语言来描述电灯开关是开着还是关着,但它无法跟踪电灯被打开或关闭的次数。
上面的机器可以知道它当前的状态是什么,是开还是关,但它不知道它的开关历史是什么(也就是说,它不知道开关被打开或关闭了多少次)。
有限自动机生成或建模规则语言。这意味着常规语言可以用一个简单的状态机图来描述。有限状态机, 描述一种给定的语言, . 据说接受一个字符串 如果机器在启动状态下启动,经历一系列状态转换,最后进入接受状态。我们说机器 认识到的语言 如果 接受所有字符串 都在 .如果一种语言有一个有限的自动机来识别它,那么它就是一种常规语言。
例如,这台机器可以识别有偶数个零的字符串的语言,因为任何有偶数个零的字符串都将从开始状态进入接受状态。
常规语言操作
常规语言可以由一串符号和操作表示。
连接
串联是一种组合两个符号、集合或语言的操作。有两种主要的方法来编写连接。 而且 两者都表示“X与y相连”。语言也可以相连: 表示来自 先写,然后字符串从 来后。
在形式上,连接的定义如下: .
联盟
联盟是一种操作,其中有限状态机可以在任何步骤中做出一个或另一个选择(这也可以被认为是一个“或”操作)。例如,可能存在一个有限状态机,可以在连接之间进行选择 与 或连接 与 .Or用竖条表示,上句中的表达式是这样的: .
形式上,union的描述如下: .注意,这里竖条的意思是“这样”。
克林星号
Kleene星号是一个用星号表示的操作 这基本上代表了重复的自我连接。例如,如果一种语言 表示窗体的所有字符串 这种语言包括 , , , 等。克林星可以重复它所操作的符号任意次数。
常规语言 表示“X与重复多次的Y或Z连接”形式的字符串。
形式上,Kleene星的定义如下: .克林星是a一元运算因为它只对一件事而不是两件事起作用(不像联合和连接,它们是二元运算).
因为 可以 , 可以重复 次了。这意味着空字符串始终是的成员 .
空字符串
另一个重要的符号是 它表示空字符串。
语言符号
语言通常是这样写的: 这里竖条的意思是"这样"模式通常类似于这样的东西 其中指数实际上表示一个一元操作- 会重复出现 次了。例如, 写成 .
正则语言、有限自动机和正则表达式之间的翻译
有限自动机和正则表达式是表示正则语言的不同方式。
有限自动机可用于在常规语言中生成字符串。特定语言的有限自动机在某种程度上是“编程的”,通过其状态和转换函数生成给定语言的字符串。您可以遍历有限状态机,查看可以生成哪些字符串,从而成为机器描述的语言的一部分,或者您可以向它提供一个输入字符串,以查看机器是否可以生成给定的输入。
注:符号为 ,表示空字符串上的转换,有时称为“空转换”。这意味着机器可以进行这些转换,而不需要读取输入上的特定符号。
一个正则表达式是将常规语言表示为字符串的一种方法。例如,正则表达式所描述的正则语言 意思是字符串要么包含任意个数的0后跟一个1,要么包含任意个数的1后跟一个0。这个正则表达式可以用下面的有限状态机表示:
正则表达式 ,这是一种以任意数量的“01”子字符串开头,后面跟着两个“1”,然后是任意数量的“10”子字符串的字符串语言,可以用以下有限状态机表示:
描述这个有限状态机的正则表达式是什么?
开始状态是 接受状态是 .从 我们可以通过循环返回on来生成1 ,我们可以这样做很多次;我们可以通过循环返回on来生成0 ,我们可以这样做很多次;或者我们可以通过转换到得到一个0 .一旦我们进入 ,通过循环返回on,我们可以生成任意数量的0 .
因此,描述它的正则表达式是 .
形式定义与语言正则性的证明
一套基于特定字母表的常规语言, 递归定义如下[2]:
空语言和空字符串是常规语言。
对于每一个 单例语言 是一种常规语言。
下一节中描述的闭包规则适用于常规语言。
没有其他语言 是常规的。
要证明一种语言是否是常规语言,只需提供生成它的有限状态机。如果给定语言的有限状态机不明显(如果一种语言实际上是非规则的,这种情况肯定是存在的),则常规语言的抽运引理是一个有用的工具。要查看非常规语言,请查看被识别的语言种类上下文无关文法或图灵机-这两种语言都能识别常规语言等等。
常规语言的抽运引理:
常规语言的抽运引理背后的思想是,为了成为常规语言,一种语言必须遵守某些约束。您可以使用泵浦引理来测试是否所有这些约束都适用于特定的语言,如果不适用,您可以用矛盾来证明该语言是非正则的。
的常规语言的抽运引理说明如果是一种语言 是否规则,是否存在整数抽运长度 这样每个字符串 长度为 或者更多的符号, ,可以写成 在哪里 的子字符串。 这样
所有常规语言都是“可泵入的”,这意味着常规语言约束的泵入引理对所有常规语言都适用。如果一种语言是不可泵浦的,那么它就不是常规语言。然而,如果一种语言是可泵的,它就不一定是常规语言。
本质上,抽吸引理包含任意长的弦 是否可以在不产生语言之外的新字符串的情况下抽取或重复片段 .
要证明一种语言是非规则的,请使用反证法还有抽吸引理。建立一个证明来证明 是正则的,并且表明抽运引理约束的矛盾至少出现在上面列出的三个约束中的一个。
用抽吸引理来证明 不是一种常规语言。
为了矛盾起见,假设 是一种常规语言。通过抽运引理,存在一个整数抽运长度 为 .我们需要一个字符串 它大于等于的长度 .当然 比 ,所以我们选择这个 字符串。这 是在 因为它已经 的年代, 的年代。
现在通过抽吸引理, .字符串中有三个可能的位置可以赋值 :
- 对于一些 .这意味着 纯粹包含在 的部分。
- 对于一些 .这意味着 纯粹包含在 的部分。
- 对于一些 而且 在哪里 这意味着 段包含在 的年代, 的部分。
在这三种情况中,我们可以很容易地验证抽运引理的第三个约束, ,不成立。换句话说,对于这三个选项中的任意一个 ,字符串 不能以一种方式抽运,导致字符串具有相等数量的 的年代, 的 语言的定义
让我们以一个简短的字符串为例 而且 .
在第一种情况下,会有更多 比现在多 的,使得产生的,泵浦的字符串不是的成员 .如果我们泵入这个区域,就会得到绳子 字符串。 的年代, 的年代。显然,这不在语言中。类似的证明可以用于第二种情况;只要泵 区域而不是 地区。
对于第三种情况,我们做类似的事情。我们只需要在这个区域找到一个违背抽运引理第三个性质的抽运例子,因为如果语言是规则的,它需要对所有人都是可抽运的 .如果我们泵 而且 最后一个泵 在 部分和前两个 在 Section,我们得到这个字符串: 一根有六个的弦 s和7 的字符串,这显然不是具有相等数量的字符串的语言 的年代, 的年代。
关闭属性
常规语言具有以下闭包属性。集合是关闭在一个操作下,如果对给定集合进行操作总是产生同一集合中的一个成员。这意味着如果将这些封闭操作中的一个应用于常规语言,则结果也将是常规语言。
- 联盟:常规语言在联盟操作。这意味着如果 而且 那么这两种都是常规语言吗 也是一种常规语言。
自 而且 都是常规语言,根据定义有一个有限状态机来描述它们;调用这些 而且 .
如果我们制造一台机器 从 而且 时,机器将接受给定的输入字符串 如果任何一 或 接受 .自 模拟 而且 如果任何一方都接受 或 接受,这意味着它将接受的并集 而且 .
这里是这样一台机器 看起来像:
- 十字路口:常规语言在十字路口操作。这意味着如果 而且 那么这两种都是常规语言吗 也将是常规语言。
就像在并包证明中,构造一个机器 这是由 而且 它接受 而且 ,分别。 运行 而且 机器在并行和接受,如果两者 而且 接受。
- 连接:拼接操作关闭常规语言。这意味着如果 而且 那么这两种都是常规语言吗 也将是常规语言。
这个证明类似于并集下闭包的证明。首先,把 接受 而且 接受 .我们怎样才能把这两台机器连接起来呢 接受
在联合中,我们将有限状态机串联起来,通过交集,我们将这些机器并联起来。自串联起 而且 意味着我们从 在strings from之前 ,我们必须把这些机器组合起来,使所有的/任何的 弦是在机器产生弦之前产生的 .我们可以通过勾搭来实现 而且 像这样使用一个非确定性有限自动机:
- 克林星号:很容易看出,常规语言在星型操作下是封闭的,因为拼接是封闭的,而星型只是重复的自我拼接。
- 补充:常规语言在补语下关闭。这意味着如果 是常规语言吗 也是一种常规语言。
以状态图为例 把所有接受的状态都变成拒绝的状态把所有接受的状态都变成拒绝的状态。我们刚刚创建了一个新的有限状态机 的补充。因为有限状态机接受 在美国,英语是一种常规语言。
与其他计算模型的关系
另请参阅
参考文献
- ,一个。Buchi非确定性例子.检索2016年6月19日,从https://en.wikipedia.org/wiki/File:Buchi_non_deterministic_example.svg
- , .正规语言.检索2016年6月21日,从https://en.wikipedia.org/wiki/Regular_language
- 阿隆森。6.045自动机、可计算性和复杂性:第4讲,2011年春季.检索自2016年6月21日http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-045j-automata-computability-and-complexity-spring-2011
- 阿隆森。6.045自动机、可计算性和复杂性:第4讲,2011年春季.检索自2016年6月21日http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-045j-automata-computability-and-complexity-spring-2011
- 费奇,W. &弗里德里希,A.;人工语法学习遇到形式语言理论:概述.检索2016年6月19日,从http://rstb.royalsocietypublishing.org/content/367/1598/1933