标签: automata

下午好,

有没有人知道在.NET 中使用Levenshtein DFA(确定性有限自动机)的"开箱即用"实现(或者很容易翻译)？我有一个非常大的字典,有超过160000个不同的单词,我希望,给出一个内在的单词w,以高效的方式在Levenshtein距离中找到所有已知单词最多2个w.

当然,具有在编辑距离处计算所有可能编辑的功能,给定单词中的一个并将其再次应用于这些编辑中的每一个解决了该问题(并且以非常简单的方式).问题是效率刍议---给予7字母的单词,这已经可以采取超过1秒即可完成,而我需要的东西很多更有效的---如果可能的话,因为它与莱文斯坦的DFA,这需要O(解决方案| w |)步骤.

编辑:我知道我可以通过一些学习来构建我自己的问题方法,但目前我无法负担阅读Schulz和Mihov长达60页的文章.

非常感谢你.

我们可以使用带后缀链接的factor-oracle(此处为纸)来计算多个字符串的最长公共子字符串吗？这里,substring表示原始字符串的任何部分.例如,"abc"是"ffabcgg"的子串,而"abg"则不是.

我已经找到一种方法来计算两个字符串的最大长度公共子s1和s2.它通过使用不在其中的字符连接两个字符串来工作,例如'$'.然后,对于s具有长度的连接字符串的每个前缀i >= |s1| + 2,我们计算其LRS(最长重复后缀)长度lrs[i]和sp[i](其LRS的第一次出现的结束位置).最后,答案是

max{lrs[i]| i >= |s1| + 2 and sp[i] <= |s1|}

我编写了一个使用这种方法的C++程序,可以|s1|+|s2| <= 200000使用因子oracle 在我的笔记本电脑上解决200ms内的问题.

s1 = 'ffabcgg'
s2 = 'gfbcge'
s = s1+'$'+s2 
  = 'ffabcgg$gfbcge'
p: 0 1 2 3 4 5 6 7 8 9 10 11 12 13
s:  f f a b c g g $ g f  b  c  g …

我正在尝试理解上下文敏感的语法,我理解为什么语言会像

1. {ww | w是一个字符串}
2. {a ⁿ b ⁿ c ⁿ | a,b,c是符号}

不是上下文,但我想知道一个类似于无类型lambda演算的语言是否与上下文相关.我想看一个简单但非玩具的例子(我考虑上面的玩具示例),一个上下文敏感语法的例子,对某些生产规则,例如,告诉一些符号串是否可以目前处于范围内(例如,在生成函数体时).上下文敏感语法是否足够强大,可以使未定义/未声明/未绑定的变量成为语法(而不是语义)错误？

我对这些东西真的很新,所以我为这里的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)很容易单独制作......任何人都可以解释一种系统的方式将它们合二为一吗？谢谢.

如何为以下语言生成正式的上下文无关语法:

{ai bjck | i != j or j != k}

我有以下作品,但无法理解:

     S->AX | YC                     unequal b’s c’s or a’s b’s

     A-> aA | e                     0 or more A’s

     C -> cC |e                     0 or more c’s

     B -> bB | e                    0 or more B’s

     X -> bXc | bB | cC             equal b’s, c’s then 1+ b’s, 
                                    1+C’s (i.e. unequal b’s and c’s)

     Y -> aYb | bB | aA             unequal a’s b’s

任何人都可以帮助我理解和解决这个问题吗？

最近我遇到了先查找后跟踪的问题

S->cAd
A->Ab|a

在这里，我对 A 的第一个感到困惑，哪个是正确的 {a} ， {empty,a} ，因为 A 的产生式中存在左递归。我很困惑是否在 A 的第一个中包含空字符串 任何帮助将不胜感激。-------------已编辑----------------

第一个和接下来的是什么，，这是我见过的如此令人困惑的语法

S->SA|A
A->a

我需要使用解析表证明这个语法不在 LL(1) 中，但无法做到，因为我没有在单个单元格中获得 2 个条目。

在正式语言的乔姆斯基分类中，我需要一些Non-Linear, Unambiguous and also Non-Deterministic上下文无关语言（N-CFL）的例子吗？

1. 线性语言：对于哪些线性文法是可能的（？CFG）例如
   L ₁ = {a ⁿ b ⁿ | ? 0 }

2. 确定性上下文无关语言（D-CFG）：对于哪些确定性下推自动机（D-PDA）是可能的，例如
   L ₂ = {a ⁿ b ⁿ c ^m | ? 0，米？0 }
   L ₂是明确的。

非线性的CF 文法是非线性的。
L _nl = {w: n _a (w) = n _b (w)} 也是一个非线性 CFG。

-- 3. Non-Deterministic Context Free Language(N-CFG) : 对于哪个only Non-Deterministic Push-Down-Automata(N-PDA)是可能的，例如
L ₃ = {ww ^R | ? {a, …

我需要一些泵浦引理问题的帮助.

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).

这是正确的吗 ？我是在"正确的道路上"吗？

谢谢

所以我正在研究我已经提出的下推自动机和无上下文语言的测试,我坚持这个结构.

我让这个自动机的每个部分都完全正常工作,除了我将在下面解释的一个部分.

它需要识别的语言是:{x#y#z#w | x,y,z,w在{0,1} +中,其中x≠w且y≠z}.

所以我遇到的问题是将Xi与Wi进行比较,因为Wi的元素在自动机处理W时是不知道的,就像我设计的那样.

如果我存储X的内容,当弹出时间并将每个元素与W的元素进行比较时,它们将以相反的顺序弹出,因此认为000111和111000是相同的字符串,而PDA将拒绝,当它应该明确接受(它们是不同的字符串).这只是一个例子,这也会导致错误地分析其他输入.

如果有一种方法可以按相反的顺序将X的内容压入堆栈,它们将以原始形式弹出,这样我就可以正确地比较字符串的内容.

如果在正常推送后有一种方法可以反转堆栈的内容,这也可以让我得出解决方案.

任何帮助将不胜感激.谢谢.

我正在 Haskell 中实现一个非确定性有限自动机，我正在尝试实现计算 epsilon 闭包的函数。为此，NFA 实现为：

data Transaction = Transaction {
     start_state :: Int, 
     symbol :: Maybe Char, 
     end_state :: Int
} deriving Show

data Automaton = Automaton {
     initial_state :: Int, 
     states :: Set.Set Int,
     transactions :: [Transaction],
     final_states :: Set.Set Int, 
     language :: Set.Set Char
} deriving Show 

而关闭：

--Perform the computations necessary to eclosure
getClosure :: [Transaction] ->  [Int]
getClosure [] = []
getClosure [tr] = [end_state tr]
getClosure (tr:trs) = end_state tr : getClosure trs 

--Get …