我想测试两种语言是否有共同的字符串.这两种语言都来自下面描述的常规语言的子集,我只需要知道两种语言中是否存在字符串,而不是产生示例字符串.
该语言由类似glob的字符串指定
/foo/**/bar/*.baz
其中**匹配0个或更多字符,并*匹配零个或多个不是的字符,/所有其他字符都是字面值.
有任何想法吗？
谢谢,迈克
编辑:
我正在研究一个问题(从介绍到自动机理论,语言和计算机,由Hopcroft,Motwani和Ullman编写)来编写一个正则表达式,它定义了一个由不包含子字符串的所有0s和1s 字符串组成的语言011.
答案(0+1)* - 011是否正确？如果不是这个应该是什么正确的答案？
我有一些格式错误的XML,我必须解析.无法解决上游问题.
(当前)问题是&符号并不总是正确转义,所以我需要转换&成&
如果&已经存在,我不想将其更改为&amp;.一般来说,如果任何格式良好的实体已经存在,我不想破坏它.我不认为通常可以知道可能出现在任何特定XML文档中的所有实体,所以我想要一个&<characters>;保留任何类似的解决方案.
在<characters>初始&和结束之间定义实体的一组字符在哪里;.特别是,<和>是不是原本表示XML元素的文字.
现在,在解析时,如果我看到&<characters>我不知道我是否会遇到a ;, (space), end-of-line, or another &.因此,我认为我必须记住,<characters>因为我向前看一个会告诉我如何处理原始角色的角色&.
我认为我需要使用Push Down Automaton的功能来实现这一点,我认为有限状态机不会因为我认为是内存要求而起作用 - 这是正确的吗？如果我需要PDA,那么调用中的正则表达式String.replaceAll(String, String)将无法工作.或者是否有可以解决此问题的Java正则表达式？
请记住:每行可能有多个替换.
(我知道这个问题,但它没有提供我正在寻找的答案.)
我被赋予了检查这种语言是否正常的任务:
L = {w?{a,b,c}* | where the number of a is less than the number of b+c.}
我既没有找到正则表达式,也没有找到确定性(或不是)有限状态自动机.另一方面,我没有找到任何方法来证明与泵浦引理定理相反.
有任何想法吗？
我想绘制一个带有边缘和圆形状态的自动机,像这样http://pop-art.inrialpes.fr/~girault/Cours/Automates/td5.html,你有一个例子吗？
我需要一些泵浦引理问题的帮助.
L = { {a,b,c}* | #a(L) < #b(L) < #c(L) }
这是我到目前为止所得到的:
y = uvw is the string from the pumping lemma.
我让y = abbc ^ n,n是泵浦引理的长度.y在L中,因为a:s的数量小于b:s的数量,并且b:s的数量小于c:s的数量.
我让u = a,v = bb和w = c ^ n.| UV | <y,如抽水引理中所述.如果我"抽"(bb)^ 2然后我得到
y = abbbbc^n which violates the rule #b(L) < #c(L).
这是正确的吗 ？我是在"正确的道路上"吗？
谢谢
P := {F, Q \ F};
W := {F};
while (W is not empty) do
choose and remove a set A from W
for each c in ? do
let X be the set of states for which a transition on c leads to a state in A
for each set Y in P for which X ? Y is nonempty do
replace Y in P by the two sets X ? Y and Y \ X
if Y is …鉴于以下语言:
L1 = { (ab)n | n ≥ 0 }
那是, L1 = { ε ab, abab, ababab, abababab, ... }
问题是要找到什么语言.L12
我的猜测是它等于.那是对的吗？如果是这样,我该如何证明呢？如果没有,为什么不呢？{ (ab)2n | n ≥ 0 }
谢谢!
math automata finite-automata regular-language formal-languages
所以我正在研究我已经提出的下推自动机和无上下文语言的测试,我坚持这个结构.
我让这个自动机的每个部分都完全正常工作,除了我将在下面解释的一个部分.
它需要识别的语言是:{x#y#z#w | x,y,z,w在{0,1} +中,其中x≠w且y≠z}.
所以我遇到的问题是将Xi与Wi进行比较,因为Wi的元素在自动机处理W时是不知道的,就像我设计的那样.
如果我存储X的内容,当弹出时间并将每个元素与W的元素进行比较时,它们将以相反的顺序弹出,因此认为000111和111000是相同的字符串,而PDA将拒绝,当它应该明确接受(它们是不同的字符串).这只是一个例子,这也会导致错误地分析其他输入.
如果有一种方法可以按相反的顺序将X的内容压入堆栈,它们将以原始形式弹出,这样我就可以正确地比较字符串的内容.
如果在正常推送后有一种方法可以反转堆栈的内容,这也可以让我得出解决方案.
任何帮助将不胜感激.谢谢.
automata non-deterministic pushdown-automaton automata-theory