automata-theory

2熱度

2回答

您是否知道任何實現像圖靈機和有限狀態自動機這樣的抽象機器的編程語言？即，過程中的以下輸入： 5元組（The notorious ⟨Q,Σ,δ,q0,F⟩ from formal languages 101），一個用於7-tuple圖靈機或抽象機的任何其它形式表示。輸入單詞。並告訴我輸入的單詞是否爲接受單詞。感謝，亞當

0熱度

1回答

有限狀態機的典型字母大小是什麼？

不太確定這是否是正確的論壇，但在理論計算機科學上建議我在此處將其移動... 有限狀態機的典型字母大小是多少？我目前正在忙於實施高性能FA庫，需要在繼續之前進行一些設計考慮。我的狀態空間大約是2 147 483 647（Integer.MAX_VALUE），我覺得這已經足夠了，即使是非常用也是如此。現在，剩下的就是字母表空間。假設字母表通常只包含所有可顯示的字符（在這種情況下，它可以存儲爲byt

1熱度

1回答

是否有一種從上下文敏感語法轉換爲線性有界自動機的算法？

我正在學習LBA（線性有界自動機）。試圖找出如何解決一些exersise。所以我想知道是否有一個簡單的方法來使LBA給出一個語境敏感的語法。這就像你如何從LR語法到DFA（確定性有限自動機）一樣。在此先感謝

2熱度

2回答

集合理論中的concat表示法

我正在爲自動機理論類做功課。到目前爲止，它的正則表達式並沒有太瘋狂。無論如何，我的問題是這是什麼是串聯適當的設置符號？例如，我知道R + S與R union S是一樣的，但對於我的生活，我不記得集合理論等價於串聯。我不會發布任何問題，因爲我認爲我會很好地處理它們，任何人都可以在正確的方向上給我一點點推動力嗎？

1熱度

2回答

什麼常規語言與1 * 0 *相交給出1n0n

我正在閱讀一本關於自動機理論的書，書中給出了一個例子，一個具有相同數量0和1的語言與1 * 0 *相交會導致1n0n，這裏n> 0 所以我的問題是，我怎麼能找到一些正則語言，當與1 * 0 *相交，也會導致1n0n。有沒有辦法考慮這個問題？更新：感謝您的答案！我想我想找到的是一些常規語言，所以像1n0n的那些不會工作;）這可能嗎？有任何想法嗎？