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