【形式語言與自動機】有限狀態(tài)機

一、有限狀態(tài)機

其需求來自于對語言字符串識別的需要，給定字符串判定它是否屬于語法G產(chǎn)生的 L(G), 判斷是否屬于這個集合。

句子識別

〉 給定一個字符串，判定是否屬于給定語法G 的語言L(G)
〉 一般來說，這是個難解的問題，并不是有一個確定的過程，實際上它涉及到上節(jié)講的語法分析有關(guān)，給出句子的構(gòu)造過程，與形式系統(tǒng)中公式的證明類似。對于判定某個句子是否屬于某個指定的語言。給出一個構(gòu)造過程，涉及到識別與判定過程。
〉 但是對于三型文法，即正則語法和正則語言來說，可以通過一個較簡單的“識別機器”來判定的，即有限狀態(tài)機。如下圖所示：
   

左邊是輸入，中間是機器，經(jīng)過機器處理之后，它會給出一個 Yes 或 No. Yes 代表著句子被接受了，復合語法，No 反之。

 機器 machine ：

實際上除了常見物理意義上的實體機器，之外我們知道有個英文單詞叫 mechanism 機制，
〉 所以針對一個系統(tǒng)，接受

總結(jié)

以上是生活随笔為你收集整理的【形式语言与自动机】有限状态机的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。