标签: regular-language

在阅读了RE/NFA和DFA之后,似乎找到一个字符串中的子字符串实际上可以使用RE而不是强力O(mn)查找渐近地更快.我的理由是DFA实际上会保持状态并避免不止一次地处理"haystack"中的每个字符.因此,如果使用正则表达式,长字符串中的搜索实际上可能会快得多.

当然,这仅适用于从NFA转换为DFA的RE匹配器.

在使用RE而不是强力匹配器时,有没有人在现实生活中经历过更好的弦乐匹配表现？

通常在我们的工作中,我们在捕获或匹配操作中使用正则表达式

但是,可以使用正则表达式 - 至少手动 - 来生成与正则表达式匹配的合法句子.当然,一些正则表达式可以匹配无限长的句子,例如表达式.+.

我有一个问题可以通过使用正则表达式句子生成算法来解决.

在伪代码中,它将运行如下:

re = generate("foo(bar|baz)?", max_match = 100);  #Don't give me more than 100 results
assert re == ("foobar", "foobaz", "foo");

什么算法会为我执行此操作？

我很好奇哪些(如果有的话)现实世界的编程语言都有常规语法(即所有语法正确的程序集是常规的).

另请参阅此问题:哪些编程语言不受上下文限制？.

?: Q × ? ? Q用英语怎么说？描述什么×和?意思也会有所帮助.

任何人都可以帮助我区分常规语言(即那些可以用正则表达式描述的语言)和其他常规语言正式定义不常规的语言吗？此外,你能否提供双方的一些例子？

我正在为我的编译器类做一些功课,我有以下问题:

写的所有串的正则表达式一个的和b含有奇数个的一个的或奇数的b的(或两者).

经过大量的白板工作后,我想出了以下解决方案:

(aa|bb)* (ab|ba|a|b) ((aa|bb)* (ab|ba) (aa|bb)* (ab|ba) (aa|bb)*)*

但是,这是我能得到的最简化的吗？我已经考虑构建DFA,试图最小化那里的状态数量,看看它是否会帮助我简化,但我想我会首先询问正则表达式专家.

这是一个计算机科学问题,而不是编程问题,但我认为这是所有相关网站中最好的问题.

当我发现正则表达式并查找该术语时,我认为这种"规律性"属性指的是表达式语言具有可定义的结构模式.然而,在阅读有关主题及其背后的理论时,我了解到有些语言不规则,但从定义它们的方式来看,很清楚模式可以与它们匹配.一种这样的语言是(a ^ n)(b ^ n).显然这是一种模式,但这不是一种常规语言.所以现在我想知道常规语言是什么使它们成为常规语言,这种语言不是吗？

Pumping Lemma用于证明语言不规律.但是如何
证明一种语言是规则的？特别是,

Let L be a language. Define half(L) to be  
{ x | for some y such that |x| = |y|, xy is in L}.  
Prove for each regular L that half(L) is regular.  

是否有任何技巧或一般程序来解决这类问题？

我有这种语言L只包含一个字符串: 写得更简洁

这个字符串有2(2 ^ n-1)个字符,我想减少它.我正在考虑使用交集,如果我能找到一些常规语言,其正则表达式的交集将产生这个字符串.

我在这里有递归函数,以防有助于:

function recursiveRegex(charset) {
if(charset.length == 0) {
    return [];
} else {
    var char = charset.splice(charset.length - 1, 1);
    var returnVal = recursiveRegex(charset);
    return returnVal.concat(returnVal) + char ;
}
}

console.log(recursiveRegex(['a1', 'a2', 'a3', 'a4']));

我在一本关于可计算性的书中读过这篇文章:

(Kleene定理)当且仅当它可以通过应用三个运算联合,连接,重复有限次数从有限语言获得时,语言是规则的.

我正在与"有限语言"斗争.

考虑这种语言: L = a*

它不是有限的.它是一个{0, a, aa, aaa, ...}显然是无限集(0=空字符串)的集合.

所以这是一种无限的语言,对吗？也就是说,"无限集"意味着"无限语言",对吧？

显然,这a*是一种常规语言.它是一种无限的语言.因此,通过Kleene的定理,它不能成为常规语言.矛盾.

我糊涂了.我想我不知道"有限语言"是什么意思.