是^ i^2 | i> = 1常規？

Question

雖然這種表達，是由確定性有限自動接受，但如果我們將這個表達式泵引理，泵引理失敗了，也該表達具有有限的國家，但不會暫停和連續運行上，邊緣不斷進行自我循環B /隨着我趨於變大，當趨於無窮時，它不應該停止。 因此，對於這種表達式，可以繪製DFA，但是抽取引理和TM失敗。 那麼，說這是一個正規的語法還是不正確？

Answer 1

實際上一個DFA無法繪製（至少一個正確的即是）。你說得對，這個抽象引理給出了一個矛盾，很容易上下推動它，使其不是正方形。如果抽象引理顯示語言不規則，那麼根據定義，無法繪製DFA來表示該語言。

的狀態集合是無限的，必須有一個狀態到接受^ 1，一個用於^ 2，一個用於^ 3等。然後是所有這些接受者之間的狀態......它很快就會變得混亂。無論如何，如果抽象引理顯示語言不規則（假設您正確應用），那麼沒有DFA（或正則表達式）來表示語言。