希望你幫我這個....問題和DFA
我這是「」如何判斷一個正則表達式將NFA和/或DFA接受的主要問題？
例如，我的問題是說哪個正則表達式是等價的？解釋... 1.（A + B）** B（A + B）** B（A + B）*
2.A BA BA *
3.A BA b（a + b）*
我們是否必須繪製NFA和DFA，然後通過最小化算法找到？如果我們這樣做，那麼我們如何才能知道NFA/DFA接受哪個正則表達式，以便我們可以從答案開始？它很混亂......
其次是一個非常相似的問題，該問題讓我表明語言（a^nb^n | n> 1}不被DFA接受... grrrrr ...我怎麼知道呢？（順便說一句，這是一組，其中後跟相同數量的b的的數量的的所有字符串的）....
我希望我解釋清楚以及....
如果你被要求表明，一些語言不是由DFA/NFA接受你幾乎總是有應用pumping lemma，這是used exactly for that purpose。
的NFA和DFA的接受當量（REG ular）語言，因此表明語言經常使用的一種方法是爲其創建NFA或DFA。
爲了表明語言不在課堂上，您通常會使用抽象引理。
除非n> = 0，否則Wikipedia有一個非常相似的例子;不過，我不會爲你完成作業。
http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages
要確定兩個正則表達式是不等價的，創建一個由一個公認的，而是由其他拒絕的字符串。
首先，關於術語的說明：語言是一組字母上的字符串。 DFA和NFA識別常規語言，而不是常規表達式。可能有幾個正則表達式定義相同的語言。對於兩種語言L1和L2，如果L1中的每個成員都是L2的成員，反之亦然，則L1和L2是等價的。
關於你的第一個問題，語言L1由{a，b}上的所有字符串組成，至少至少兩個'b'。語言L2由{a，b}上的所有字符串組成，其中正好爲兩個'b'。 字符串「abbb」是L1和L3的元素，但不是L2。因此，L1和L3 進行比較。任何L1的元素S必須包含至少兩個'b'。讓S中的前兩個'b的 與表達式E3中的兩個顯式'b'匹配;那麼其他組件a*,a*和(a+b)*總是可以匹配的，並且S必須在L3中。因此L1是L3的一個子集。類似地，L3的任何元素S必須包含至少兩個「b」。讓那些符合表達式E1中兩個明確的'b';其他組件(a+b)*,(a+b)*,(a+b)*也將 有匹配，並且S也在L1中。所以L1是L3的一個子集，L3是L1的一個子集，所以L1和L3必須是等價的。
關於你的第二個問題：使用pumping lemma。假設您有一個接受該語言的DFA ...表明它也必須接受不在該語言中的字符串，因此不能存在此類DFA。假設S是語言中的任何字符串...... S的任何子字符串都可以包含所有的a，b，或者兩者都有......那麼在你「泵」它之後會發生什麼？
感謝Jim .....太多了....我試過了，但是可以在第二個上再投光一些.....再次感謝...... – Lopa 2010-04-24 03:41:57
@Loop：假設DFA有n個狀態，但接受任意長的字符串的語言。那麼DFA必須有一個循環，並且該循環具有n個或更少的狀態轉換。因此，任何輸入字符串都會在該循環中使用DFA，並且可以「抽取」（重複）任意次數的子字符串，並且仍然可以被DFA接受。 – 2010-04-24 03:49:27
嗨......是不是有任何簡單或簡短的方式表明DFA/NFA的接受度？ – Lopa 2010-04-24 02:49:36
@Loop：顯示一種語言被接受，並表明它不能被接受是兩種不同的問題。這個'a^nb^n'問題的意圖當然是你使用抽象引理。 – sth 2010-04-24 02:59:16