”“”

自動機，語言和計算理論簡介

計算機理論，自動機理論，形式語言和自動機理論

本課程的目的是“自動化，語言和計算理論的簡介”，是為每個數學模型，它們各自的語言及其可靠的等價性提供全面的解釋。 “計算機理論”的領域可以分為三個主要細分：1）自動機理論，2）計算理論和3）複雜性理論。自動機理論重點介紹了類似於編程機的數學模型，該模型會自動執行操作。有四個主要的數學模型：有限自動機（AF），堆棧自動機（AP），有限的磁帶自動機（AFL）和Turing Machine（MT）。每個模型都根據其內存單位而不同。 AF沒有外部內存單元，AP具有堆棧作為內存單元，AFL具有有限的長度膠帶作為內存單元，MT的磁帶作為內存單元。每個模型都根據其內存單元的局限性解決了有限的問題。每個模型解決的問題集被歸類為模型接受的語言。有限自動機解決的問題稱為常規語言，其相應的語言表示稱為常規語法。堆棧自動機接受的語言被稱為無上下文語言，有限磁帶自動機接受的語言稱為上下文敏感語言和圖靈機所接受的語言，稱為無限制的語言，因為圖靈機器人具有無限的內存，並且隨機訪問了內存的隨機訪問單元。可以將圖靈機與現代計算機進行比較，因為它們可以解決任何計算機解決問題。計算理論的重點是驗證問題是否可以解決，而復雜性理論涉及Turing Machine可以解決的解決方案的算法複雜性。本課程主要關注自動機理論（數學模型）及其語言。

您將學到什麼

• 對自動機，語言理論及其重要性的基礎有深入的了解
• 了解有限自動機，電池自動機和圖靈機的操作
• 使用有限自動機，電池自動機和圖靈機制定解決問題的技能
• 識別各種自動機之間的關係
• 重視證明自動機之間等價的重要性

“”