您如何證明有序的語言是正常的？

我想知道如何證明有序約束的語言是常規的。例如，如果你有Σ= {1,2,3,4,5}，其中L（Σ*的一個子集）=（a1，a2，... an）使得+ 1大於你證明這是一種常規語言？您如何證明有序的語言是正常的？

例如α=（1,3,5）將被接受，然而α=（1,4,5,2）不會。

2013-10-29 Quanqai

DFA（確定性有限自動機）可識別的任何語言都是常規語言。爲了證明您描述的語言是正規的，您只需證明存在識別此特定語言的DFA即可。

請記住Σ是有限的。如果我正確理解了語言的約束條件，那麼一個工作的結構將會有一個起始狀態（接受還是不接受，取決於您是否希望在您的語言中包含ε），一個接受Σ中每個符號的狀態和一個拒絕狀態。如果當前狀態是開始狀態或對應於「較小」符號，則轉換函數應導致與當前輸入符號相對應的狀態，否則將導致與拒絕狀態相對應的狀態。

快捷方式也是可用的 - 每種有限語言都是規則的，如果我理解了適當描述的語言的約束條件，它顯然是有限的（因爲Σ是有限的）。這簡單意味着語言也是常規的。

來源

2013-10-29 23:22:58 kviiri

這是我試圖證明的語言的簡化版本是經常性的，我正在尋找一個我可以應用於更困難的問題的概念。您所描述的方式是我如何嘗試爲我的問題繪製DFA，但我遇到了需要加星標的問題（我認爲）。在更復雜的情況下，有這樣的順序約束，但與數字不同的是，例如，p可以跟隨r，t可以跟隨p，但是r可以跟隨t。但是，由於我完全忘記了拒絕狀態以使其完成，所以您的洞察力很有幫助:) – Quanqai

無論如何，相同的一般解決方案都適用：如果您可以構建DFA或NFA來描述語言，那麼它是常規的。使用Kleene星不應該是一個問題，因爲修改自動機以接受其原始語言的星形版本非常容易 - >如果A是A *，則A *是常規的。如果更容易，您可能還想證明該語言是多種常規語言的聯合。常規語言通過聯合運算符關閉，因此產生的語言也是常規的。 – kviiri

我認爲把語言分解成更小的DFA，然後將它們結合起來可能是我最好的選擇。謝謝您的幫助。 – Quanqai

您如何證明有序的語言是正常的？

回答

相關問題