标签: regular-language

语言0 ^m 1 ⁿ的正则表达式是什么,其中m + n是偶数？

我有一个正则表达式,它是计算机程序的输出.它有类似的东西

(((2)|(9)))*

人类毫无疑问会把它写成

[29]*

所以我想要一个程序可以进行简单的转换,使正则表达式更具可读性.到目前为止,我一直在使用快速脚本

$r =~ s/\(([0-9])\)/$1/g;
$r =~ s/\(([0-9])\|([0-9])\)/[$1$2]/g;
$r =~ s/\(([0-9]|\[[0-9]+\])\)\*/$1*/g;
$r =~ s/\((\[[0-9]+\]\*)\)/$1/g;
$r =~ s/\|\(([^()]+)\)\|/|$1|/g;

减少长度,但结果仍然包含像

(ba*b)|ba*c|ca*b|ca*c

应简化为

[bc]a*[bc]

我搜索了CPAN并找到了Regexp :: List,Regexp :: Assemble和Regexp :: Optimizer.前两个不适用,第三个有问题.首先,它不会通过它的测试,所以我不能使用它,除非我force install Regexp::Optimizer在cpan.其次,即使我这样做,它也会扼杀表达.

注意:除了[regex]之外,我还标记了这个[常规语言]因为正则表达式只使用连接,交替和Kleene星,所以它实际上是常规的.

我在解决/证明这个问题时遇到了麻烦.有什么想法吗？

我的问题听起来可能与你有所不同.

我是初学者,我正在学习有限自动机.我正在互联网上搜索下面给定机器的有限自动机的正则表达式.

任何人都可以帮我写上述机器的"有限自动机的正则表达式"

任何帮助将不胜感激

我想在基于 DFA 的正则表达式匹配器中实现“词边界”匹配。有人能告诉我这是怎么做的吗？

提供一些背景知识，我目前正在使用“dk.brics.automaton”库，但它不支持断言（例如\b，词边界）。我需要使用基于 DFA 的引擎，因为我的主要目标实际上是确定正则表达式的等效性，而不是进行实际匹配。

此外，以下问题的答案似乎表明这是可能的： 基于 DFA 的正则表达式匹配 - 如何获取所有匹配？ 说

“同样，我们通过向模拟器添加带有特殊指令的 epsilon 转换来管理它。如果断言通过，则状态指针继续，否则将被丢弃。”

然而，我不太明白这意味着什么。它是否暗示它只能使用一种特殊类型的 epsilon 转换来完成，该类型查看其端点并且只有在其端点满足断言时才能遍历，或者可以使用以某种方式配置的“正常”epsilon 转换来完成？如果我需要这些“特殊”类型的 epsilon 转换，那么如何确定这些转换（即转换为标准 DFA）？

非常感谢有关如何实际实现这一点的任何描述的指针。

我相信这种语言不是上下文,因为PDA不可能比较2个0和1的相同长度的块,并且还记住它的长度以供以后使用.

不幸的是,我不知道如何证明它.

我尝试使用泵浦引理无济于事......

我还试图通过矛盾来假设语言是无上下文的,并且使用这样一个事实,即上下文无关语言与常规语言的交集也是无上下文的(通过找到一些神秘的常规语言L),并且令人惊讶(或者不是) ) - 我所有的努力都是徒劳的......

任何帮助,将不胜感激

这篇文章说：

像 \1 或 \2 这样的反向引用匹配由前面带括号的表达式匹配的字符串，并且只有该字符串： (cat|dog)\1 匹配 catcat 和 dogdog 但不匹配 catdog 或 dogcat。就理论术语而言，具有反向引用的正则表达式不是正则表达式。

为什么？出于什么原因\1成为“正则表达式”不再是“正则表达式”？

我想知道两种语言（一种是常规语言，另一种不是）之间的连接是否总是不规则的，或者输出是否可能是一种常规语言。谢谢。

我需要增加a-zA-ZáàâäãåçéèêëíìîïñóòôöõúùûüýÿæœÁÀÂÄÃÅÇÉÈÊËÍÌÎÏÑÓÒÔÖÕÚÙÛÜÝŸÆŒx时间，但是我觉得这很丑。所以我尝试了，\p{L}但是在JavaScript中不起作用。

任何的想法 ？

我的实际正则表达式： [a-zA-ZáàâäãåçéèêëíìîïñóòôöõúùûüýÿæœÁÀÂÄÃÅÇÉÈÊËÍÌÎÏÑÓÒÔÖÕÚÙÛÜÝŸÆŒ][a-zA-ZáàâäãåçéèêëíìîïñóòôöõúùûüýÿæœÁÀÂÄÃÅÇÉÈÊËÍÌÎÏÑÓÒÔÖÕÚÙÛÜÝŸÆŒ' ,"-]*[a-zA-ZáàâäãåçéèêëíìîïñóòôöõúùûüýÿæœÁÀÂÄÃÅÇÉÈÊËÍÌÎÏÑÓÒÔÖÕÚÙÛÜÝŸÆŒ'",]+

我想要一个类似的东西：（[\p{L}][\p{L}' ,"-]*[\p{L}'",]+或小于实际表达式）

我知道正则表达式包可以识别比正则语言更广泛的语言，但是在Python 正则表达式中使用递归正则表达式来查找文本字符串中的算术表达式让我想知道是否可以使用正则表达式识别任何上下文无关语言，并且如果没有，有人可以提供一个反例吗？