标签: automaton

在Haskell中表示有限自动机的好方法是什么？它的数据类型如何？

在我们学院,自动机被定义为5元组

(Q, X, delta, q_0, F)

其中Q是自动机状态的集合,X是字母表(这部分甚至是必要的),delta是从(Q,X)获取2元组并返回状态/ -s(在非确定性版本中)的转换函数, F是接受/结束状态的集合.

最重要的是,我不确定delta应该有什么类型......

假设我有一个正则表达式列表(从外部源读取 - 文件,数据库等).我想检查字符串匹配哪些正则表达式.

我可以通过所有这些正则表达式创建迭代并匹配它们,但列表可能是一个巨大的,这是一个关键的操作.

我可以将所有这些正则表达式合并为一个(在它们之间),但问题是我只能识别第一个匹配的正则表达式,而不是所有.

另一个想法可能是为所有这些正则表达式创建一个自动机,并用相应正则表达式的索引标记最终状态.我正在查看http://cs.au.dk/~amoeller/automaton/,这个库似乎能够使用正则表达式和自动机,但不确定它是否可以扩展来解决我的问题.

你还有其他建议吗？

为了澄清一些评论,我添加了一个代码示例:

import java.util.regex.Matcher;
import java.util.regex.Pattern;


public class PatternTest {
    public static void main(String[] args) {
        Pattern p = Pattern.compile("(a(?:b|c)a)|((?:a|b)ba)|(ab(?:a|c))");     
        Matcher m = p.matcher("aba");
        System.out.println(m.matches());
        System.out.println(m.groupCount());
        for (int i = 0, n = m.groupCount(); i < n; i++) {
            System.out.println(m.group(i));
        }
    }
}

将打印出来

true
3
aba
aba
null

正如您所看到的,只有第一组匹配,我没有找到匹配其他两组的方法.

更多发现 - 使用上面的自动机库,问题将减少到以下几点:如果连接两个或多个自动机,如何识别哪个原始自动机对应的最终状态？

我想在一个文本文档中搜索关键短语数据库中出现的关键短语(从维基百科文章标题中提取).(即,给定一个文档,我想找出是否有任何短语都有相应的维基百科文章)我发现了Aho-Corasick算法.我想知道为数百万条目的字典构建Aho-Corasick自动机是否有效且可扩展.

我正在为自动机理论做一个任务,我必须通过确定性有限自动机的转换函数来确定一个单词是否被接受

我有这个输入文件:

6 8 0 2
2
5
0 0 a
0 1 a
1 1 b
1 2 c
1 3 c
3 4 d
4 4 d
4 5 d
3
aaabcccc
aabbbbcdc
acdddddd

输入以4个整数开始,第一个是自动机的状态数,第二个是自动机的转换数,第三个数是初始状态,然后是最终状态数.然后是最终状态(在示例中,最终状态是2和5).

然后是N行(N是转换的数量),每个都有2个整数和一个字符I,J和C,表示转换的状态,即转换从状态i转到状态J,字符为C.在这一行之后加上一个整数S,它将包含要测试的字符串数,然后是包含相应字符串的S行.

该程序的输出应为:

Case #2:
aaabcccc Rejected
aabbbbcdc Rejected
acdddddd Accepted

它应该说是否接受或拒绝字符串.到目前为止,我只使用输入编写了工作.

我不知道如何最方便地表示自动机.我应该只使用数组吗？我将什么逻辑应用于数组？有没有办法在不事先知道自动机字母表的情况下做到这一点？我需要一个数据结构来表示自动机吗？我对这项任务感到有点困惑,并希望有一些想法,一些伪代码或想法.代码是用另一种语言编写的吗？我不想要解决方案,因为我想做我的任务但是如果我可以使用一些帮助

哪个是确定两个自动机之间等价的最佳或最简单的方法？

即,如果给出两个有限自动机A和B,我如何确定两者是否识别相同的语言？

它们既具有确定性,也具有不确定性.

我正在从一些输入数据类型到输出数据类型编写流转换器.输入由用户进行,因此事件之间有一段时间.因为每个输入都需要一些资源加载,所以我想"展望未来",即将所有可能的输入发送到主计算并根据结果预加载资源.

目前,每次输入后总会有一个输出,但最终可能会改变它.

我成功地用Ross Paterson的Automaton变压器实现了这一点.我不确定我的解决方案是否最佳.

• 有没有很好的例子如何做到这一点？也许即使有测试代码？
• 它也可以用monad实现吗？(例子？,解释为什么不可能？)

编辑:在调用更多细节后,我在这里添加了代码.现在我将其删除(这是不可理解的)并添加一些其他解释.我的问题得到了回答.

我的目的是让主事件循环在每个用户输入之后停止,这些用户输入已被馈送到箭头/流变换器/等等.然后它将存储当前自动机状态并将所有可能的输入(假事件)逐个发送到自动机,并查看必须加载哪些资源,以缓存它们.在下一个真实事件之后,它将使用缓存来获得更好的响应.主要计算不应受此影响.

我正在做一个模拟非确定性有限自动机的任务,正如我在这篇文章中解释的那样.我从文件中读取了这个输入tarea4.in:

1
6 8 0 2
2
5
0 0 a
0 1 a
1 1 b
1 2 c
1 3 c
3 4 d
4 4 d
4 5 d
5
aaabcccc
aabbbbcdc
abbcdddcc
acdddddd
abc

第一行输入是整数T,表示评估程序的个案数.每个测试用例以4个整数开始,第一个是自动机的状态数,接下来是自动机的转换数,第三个数是初始状态,然后是最终状态数.然后是最终状态(在示例中,最终状态是2和5).然后是F行,每行有一个整数E,表示E是最终状态.

然后是N行(N是转换的数量),每个都有2个整数和一个字符I,J和C,表示转换的状态,即转换从状态i转到状态J,字符为C.在这一行之后加上一个整数S,它将包含要测试的字符串数,然后是包含相应字符串的S行.

预期的产出是:

Test Case #2:
aaabcccc Rejected
aabbbbcdc Rejected
abbcdddcc Rejected
acdddddd Accepted
abc Accepted

输出导致我的代码:

Test Case #1:
aaabcccc Rejected
aabbbbcdc Rejected
abbcdddcc Rejected
acdddddd Rejected
abc Rejected

这是我的代码:

#include <iostream>
#include <vector>
#include <map>
#include …

我是线程的新手,我想知道如何使用它们在非确定性有限自动机中进行评估.

我有调用另一个方法的方法:

public bool Evaluate2(string s)
{
    accepted = false;

    ThreadEval(s, StartState);            

    return accepted; 
}

变量accepted是一个类成员,我用它来控制其他线程何时应该停止.

void ThreadEval(string s, State q)
{            
    if (s.Length == 0 && q.IsFinal)
    {
        accepted = true;
        return;
    }

    bool found = true;            
    State current = q;

    for (int i = 0; found && !accepted && i < s.Length; i++)
    {
        found = false;
        foreach (Transition t in current.transitions)
            if (t.symbol == s[i])
            {
                Thread thread = new Thread(new ThreadStart(delegate { ThreadEval(s.Substring(i+1), t.to); …

在下图中，我可以互换使用两种 NFA 吗？如果不是那么为什么？

Datalog不是图灵完备的。

但它的计算类是什么？

它相当于有限状态机或下推机（即上下文无关）……还是介于两者之间？