标签: regular-language

我正在攻读我的计算语言测试,并且有一个想法我遇到了问题.

我知道常规语法更简单,不能包含歧义,但不能完成编程语言所需的大量任务.我也理解无上下文语法允许模糊,但允许编程语言(如回文)所需的一些东西.

我遇到的问题是通过了解常规语法非终结符可以映射到终端或非终结符后跟终端,或者无上下文非终结符映射到终端和非终结符的任意组合,从而理解我如何得到以上所有内容.

有人可以帮我把所有这些放在一起吗？

我试图理解语言级别的概念(常规,上下文无关,上下文敏感等).

我可以很容易地看清楚这一点,但我发现的所有解释都是一堆符号并谈论集合.我有两个问题:

1. 你能用语言描述常用语言是什么,以及语言有何不同？

2. 人们在哪里学会理解这些东西？据我了解,这是正式的数学？我在大学有几个课程使用它,几乎没有人理解它作为导师只是假设我们知道它.我在哪里可以学到它以及为什么人们"期望"在如此多的资源中知道它？就像教育方面存在差距一样.

这是一个例子:

属于该集合的任何语言都是字母表中的常规语言.

语言怎么能"超过"任何东西？

我有一个庞大的正则表达式集合,当匹配时调用一个特定的http处理程序.一些较旧的正则表达式是无法访问的(例如a.c* ? abc*),我想修剪它们.

是否有一个库给出两个正则表达式会告诉我第二个是否是第一个的子集？

我一开始并不确定这是否具有可判定性(它的气味就像一个不同名称的停止问题).但事实证明它是可判定的.

我试图找到一个简单的(即非正式的)解释,正如乔姆斯基所阐述的4级正式语法(无限制,上下文敏感,无上下文,常规).

自从我学习正式语法以来,这已经是一个时代了,各种各样的定义现在让我难以想象.要明确的是,我不是在寻找你​​到处都可以找到的正式定义(例如这里和这里 - 我可以谷歌以及其他任何人),或者甚至是任何形式的正式定义.相反,我希望找到的是干净简单的解释,为了完整性而不牺牲清晰度.

写一个包含偶数个0或奇数个1的表达式

我把它归结为:

1*(01*01*)* + 0*10*(10*10*)*

其中第一部分表示偶数个0,第二部分表示奇数个1

但是,应该有一个我没有看到的简化解决方案.有小费吗？

我在这里看到一些评论,提到现代正则表达式超出了常规语言的表达范围.这是怎么回事？

现代正则表达式的哪些特征不规则？例子会有所帮助.

用C语言识别标识符的常规定义由下式给出

letter -> a|b|...z|A|B|...|Z|_
digit -> 0|1|...|9
identifier -> letter(letter|digit)*

该定义将生成表单的标识符

标识: [_a-zA-Z][_a-zA-Z0-9]*

我现在的问题是如何将生成的标识符的长度限制为不超过31个字符.需要在常规定义中进行哪些更改,或者如何编写正则表达式以将其限制为不超过指定的长度.有谁可以帮忙.谢谢.

我需要帮助为下面的语言构建左线性和右线性语法？

a)  (0+1)*00(0+1)*
b)  0*(1(0+1))*
c)  (((01+10)*11)*00)*

对于a)我有以下内容:

Left-linear
S --> B00 | S11
B --> B0|B1|011

Right-linear
S --> 00B | 11S
B --> 0B|1B|0|1

它是否正确？我需要帮助b&c.

我被要求显示DFA图和RegEx作为RegEx的补充(00 + 1)*.在之前的问题中,我必须证明DFA的补充是封闭的并且也是正则表达式,所以我知道要将DFA,M转换为补码,M`,我只需要交换初始接受状态和最终接受国家.

但是,似乎RegEx的初始接受状态是{00, 1, ^},最终接受状态也是{00, 1, ^}如此.因此,交换它们只会产生完全相同的RegEx和DFA,这似乎是相互矛盾的.

我做错了什么,或者这个RegEx应该没有真正的补充？

谢谢

给出一个描述常规语言的正则表达式R(没有花哨的反向引用).有没有一种算法来构造一个正则表达式R*来描述除R描述的所有单词之外的所有单词的语言？它应该是可能的维基百科说:

常规语言在各种操作下关闭,也就是说,如果语言K和L是常规语言,则以下操作的结果也是如此:[...]补语¬L

例如,给定字母{a,b,c},语言的反转(abc*)+是(a |(ac | b | c).*)？

正如DPenner在评论中已经指出的那样,正则表达式的倒数可以比原始表达式指数级大.这使得反转正则表达式不适合实现用于搜索目的的否定部分表达式语法.是否有一种算法可以保留正则表达式匹配的O(n*m)运行时特性(其中n是正则表达式的大小,m是输入的长度),并允许否定的子表达式？