标签: regular-language

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

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

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

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

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

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

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

语言0 ^m 1 ⁿ的正则表达式是什么,其中m + 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.  

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

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

(((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星,所以它实际上是常规的.

我有这种语言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']));

我对这些东西真的很新,所以我为这里的noobishness道歉.

构建一个Deterministic Finite Automaton识别以下语言的DFA:

L= { w : w has at least two a's and an odd number of b's}. 

每个部分的自动化(at least 2 a's, odd # of b's)很容易单独制作......任何人都可以解释一种系统的方式将它们合二为一吗？谢谢.

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

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

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

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

任何帮助将不胜感激

我理解正则表达式是如何得到它们的名字的,并且已经阅读了相关的问题(为什么正则表达式称为"常规"表达式？),但我仍然想知道正则表达式是否总是规则的.

例如,反向引用如何定期？这不需要一些内存,因此无法通过有限状态自动机匹配/生成吗？