nfa

2熱度

1回答

我對自動機的語言實現感到困惑。如果有一個「過渡」，自動機會直接進入下一個狀態嗎？假設我有一個自動機，它由三個狀態a,b和c（其中a爲初始狀態，c爲接受狀態）組成，並帶有字母{0,1}。以下工作如何？ a----ɛ--->(b----0---->a) (b----1---->c) 是否接受字符串「1」？如果我們有 a---1--->b----ɛ--->c ？字符串「1」會被接受

1熱度

1回答

在結構體定義中聲明一個struct的堆棧

我需要在它自己的struct聲明中聲明兩個struct的結構體。我知道我可以用一個數組來做這個操作，只要我用結構體內的指針引用它（即FA *goingTo[30];會給我一個30 FA的數組）。有沒有類似的方法來引用堆棧？ typedef struct FA { std::stack<FA> goingTo; std::stack<FA> comingFrom; };

0熱度

1回答

NFA轉化爲DFA =確定性？

我在決定論和非決定論的意義上掙扎了一下。當涉及到自動機時，我得到了不同，但我似乎無法找到以下答案：NFA轉換爲DFA轉換是否具有確定性？如果可以爲同一常規語言構建多個DFA，那麼這是否意味着NFA轉換爲DFA的結果不是唯一的？因此一個非確定性算法？我很高興你可以提供任何信息。在此先感謝！

2熱度

1回答

轉換正則表達式到DFA

我一直在試圖轉換正則表達式非確定性有限自動機（NFA）首先使用湯普森的建設，並提供：，看起來正確。然後我使用子集構造從NFA創建DFA，如下所示。但這並不看起來是正確的我，例如0，緊接着0根據我所構建的DFA無效。我想知道我應該如何對原始正則表達式中的epsilon進行建模，因爲我只是將其視爲正常的epsilon。

1熱度

1回答

無法構建4狀態NFA對某些正則表達式

在對NFA的有人問我，構建一個4狀態NFA的正則表達式的鍛鍊（AA | AAB）* B。我試圖自己構建它，並且我只能找到一個5狀態的NFA，這是一個後來證實的在線工具。（我發現它沒有（4）是最終的，並且從b的（3）到（2）有一個額外的箭頭，但是這導致了相同的結果）是我沒有看到問題，或者是沒有看到問題，有沒有辦法做到這一點只有四個國家？

0熱度

1回答

我想要接受字符串{a，b，c}的dfa，它以a開始並以c結尾，甚至沒有。 b

我爲此做了以下dfa ...但它不正確...請幫助我...有效的字符串是abbc，aabbcc，aabbbbc，abbcccc。和無效的字符串是abca，abc，abbcb，babbc.please幫助我。我已經做到了。 <?php include "config.php"; if (isset($_POST['submit'])) { include('PHPMailer

1熱度

1回答

變化

我的轉換表：這裏，形象是什麼R的R *和S *的差異和s 哪些變化應該在我的TD？我的TD：

1熱度

1回答

正則表達式範圍和組DFA實現爲表

我目前正忙於從正則表達式（沒有捕獲組沒有回溯）到表驅動DFA轉換。我通過從Regex創建NFA然後將NFA轉換爲DFA來實現此目的。我目前通過用「（a | b | ... | y | z）」代替組來處理諸如「[a-z]」之類的組，並且其工作原理和生成的DFA表仍然合理。除了abc的轉義版本之外，「[^ abc]」將被替換爲「（\ u0000 | \ u0001 | ...）」，但這會導致巨大的表格

2熱度

2回答

爲什麼在DFA上使用NFA

我正在研究一些計算理論，正如所暗示的那樣，這是非常理論的。我可以很容易地從正則表達式轉換爲NFA到DFA，我可以理解。但是由於所有的NFA都可以轉換爲DFA（我敢肯定）在UNIX中的grep命令使用正則表達式來確定匹配的字符串，最常用的有限自動機，DFA或NFA是什麼？根據我的經驗（不是很多），DFA在表示常規語言時通常要簡單得多，而且也是確定性的，因此應該總是選擇超過NFA。 NFA分支到多

-1熱度

1回答

什麼是電子關閉（r）在以下NFA

對不起，我不能在這裏提供圖片...我無法上傳圖片...所以..我會給出問題的轉換表。 (S/I)....a...b.....c.......e(elipson) p>.......{p}.....{q}...{r} ..¤(phi) q>.......{q} ....{r} ..¤.... {p} r(final)>..{r}...¤....{p}....{q} 這裏¤是班派