标签: finite-automata

嗯 - 问题是什么.这是我一直听到的,但我还没有完成调查.

(更新)我可以查看定义......但为什么不(正如@erikson指出的那样)深入了解你的真实经历和轶事.社区维基会帮助人们投票给最有见地的答案.有趣的阅​​读到目前为止,谢谢!

我正在研究一种将非确定性有限状态自动机(NFA)转换为确定性有限状态自动机(DFA)的程序.为此,我必须计算具有epsilon转换的NFA中每个状态的epsilon闭包.我已经找到了一种方法来做到这一点,但我总是认为我想到的第一件事通常是效率最低的做事方式.

这是一个如何计算简单的epsilon闭包的例子:

转换函数的输入字符串:format是startState,symbol = endState

EPS是一个epsilon过渡

1,EPS = 2

新州的结果{12}

现在显然这是一个非常简单的例子.我需要能够从任意数量的状态计算任意数量的epsilon转换.为此,我的解决方案是一个递归函数,通过查看它具有epsilon转换的状态来计算给定状态的epsilon闭包.如果该状态具有(a)epsilon转换,则在for循环内递归调用该函数,以获得与其一样多的epsilon转换.这将完成工作,但可能不是最快的方法.所以我的问题是:在Java中计算epsilon闭包的最快方法是什么？

我现在正在学习计算理论课程.我能很好地理解这些概念.我能够解决问题.而且,当我向我的导师询问真实世界的应用程序时,他告诉我这些概念在编译器设计中肯定是有用且必不可少的.但是,至少要做一个有意义的研究,我需要一些解释,如何在编码中使用这些概念.

例如,如果我想设计自己的grep.我将在C中使用字符串函数.我不知道如何在编码中使用正则表达式.

同样的情况适用于图灵机.

如果我想添加两个数字,为​​什么我必须遵循这些一元的概念.硬件是否实现了这些概念？

我正在与Ragel一起评估FSA,我想嵌入一个用户操作,只要我的机器完成测试输入就会运行.无论机器是否以接受状态结束,我都需要执行此操作.我从Ragel指南中获取了这个修改过的示例,说明了我的目标:

#include <string.h>
#include <stdio.h>

%%{
    machine foo;
    main := ( 'foo' | 'bar' ) 0 @{ res = 1; } $/{ finished = 1; };
}%%
%% write data;
int main( int argc, char **argv ) {
    int cs, res = 0, finished = 0;
    if ( argc > 1 ) {
        char *p = argv[1];
        char *pe = p + strlen(p) + 1;
        char* eof = pe;
        %% write init;
        %% write exec;
    }

    printf("result = %i\n", res …

我的问题的要点是我有一个确定性状态自动机,它根据一个移动列表进行转换,我希望这个转换序列充当另一个函数的"计算上下文".这个其他函数会在每次转换时观察状态机,并用它做一些计算,模糊地让人联想到模型视图模式.通常,这个其他功能可能只是读取机器所处的当前状态,并将其打印到屏幕上.

我的状态机实现:

data FA n s = FA { initSt1 :: n, endSt1 :: [n], trans1 :: n -> s -> n }

-- | Checks if sequence of transitions arrives at terminal nodes
evalFA :: Eq n => FA n s -> [s] -> Bool
evalFA fa@(FA _ sfs _ ) = (`elem` sfs) . (runFA fa)

-- | Outputs final state reached by sequence of transitons
runFA :: FA n s -> [s] -> n
runFA (FA s0 …

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

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

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

考虑这种语言: L = a*

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

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

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

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

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

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

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

任何帮助将不胜感激

任何人都可以举例解释有限状态机和有限自动机之间的区别是什么？

是否可以使用基于DFA的正则表达式实现捕获组,同时保持相对于输入长度的线性时间复杂度？

直觉上我想不是,因为子集构造过程不知道它可能落入哪个捕获组,但这是我第一次意识到这可能是一个潜在的问题,所以我不知道.

我已经在一个项目上工作了一个月左右,现在用javascript开发XML验证器(XSD).我已经非常接近但仍然遇到问题.

我唯一能运作良好的是将模式结构规范化为存储在DOM中的FSA.我已经尝试了几种方法来针对FSA验证我的xml结构,并且每次都变短.

验证器用于运行客户端WYSIWYG XML编辑器,因此它必须满足以下要求

• 必须高效(即使使用复杂模型,<15ms也可以验证元素子节点模式)
• 必须公开一个后验证模式信息集(PSVI),可以查询该信息以确定可以在各个点从文档中插入/删除哪些元素,并使文档保持有效.
• 必须能够验证xml子节点结构,如果无效则返回哪些内容为EXPECTED或哪些内容为UNEXPECTED.

- 更多信息请考虑以下示例 -
首先,我将模式结构转换为一般FSA表示,规范化xs:group和xs:import之类的命名空间.例如考虑:

<xs:group name="group1">
    <xs:choice minOccurs="2">
         <xs:element name="e2" maxOccurs="3"/>
         <xs:element name="e3"/>
    </xs:choice>
</xs:group>
<xs:complexType>
    <xs:seqence>
        <xs:element name="e1"/>
        <xs:group ref="group1"/>
    </xs:sequence>
<xs:complexType>

将被转换为类似的广义结构:

<seq>
    <e name="e" minOccurs="2"/>
    <choice minOccurs="2">
         <e name="e2" maxOccurs="3"/>
         <e name="e3"/>
    </choice>
</seq>

我通过XQuery和XSLT在所有服务器端执行此操作.

我构建验证器的第一次尝试是使用javascript中的递归函数.在此过程中,如果我发现可能存在的内容,我会将其添加到全局PSVI信号中,表明它可以添加到层次结构中的指定点.

我的第二次尝试是迭代的,而且速度要快得多,但这两次都遇到了同样的问题.

这两个都可以正确验证简单的内容模型,但是一旦模型变得更复杂并且非常嵌套,它们就会失败.

我想我正在从完全错误的方向接近这个问题.根据我所读到的,大多数FSA是通过将状态推送到堆栈来处理的,但我不确定如何在我的情况下执行此操作.

我需要就以下问题提出建议:

1. 状态机是否是正确的解决方案,它是否会实现顶部所述的目标.
2. 如果使用状态机是什么最好的方法将架构结构转换为DFA？汤普森算法？我是否需要优化DFA才能使其正常工作.
3. 什么是最好的方式(或最有效的方式)在javascript中实现这一切(注意优化,并且预处理可以在服务器上完成)

谢谢,

卡西

其他编辑:

我一直在看这个教程:http : //www.codeproject.com/KB/recipes/OwnRegExpressionsParser.aspx专注于正则表达式.它似乎与我需要的非常相似,但专注于为正则表达式构建解析器.这带来了一些有趣的想法.

我认为xml架构只分解为几个运算符:

sequence - > Concatination
choice - > union
minOccurs/maxOccurs - 可能需要更多Kleene Closure,不能完全确定表示此运算符的最佳方法.