我知道FSA如何接受字符串'nice'（如維基百科頁面所示），但FSA接受的語言如何成爲編程語言？作爲（編程）語言接受器的有限狀態自動機
是這樣嗎？假設我有一個字母表A = {1,2，+， - }和語言L = {1 + 1,1 + 2,1-1,1-2}，那麼我的FSA看起來像這樣;
-->[1]--1-->[2]--+-->[3]--1-->[[5]]
| |
- 2-->[[6]]
|
v
[4]--1-->[[7]]
|
2-->[[8]]
當我達到接受狀態5,6,7,8我知道值應該是什麼，因此我定義了一種編程語言？
如果我擴展它以嵌套FSA，那麼我可以計算字符串'1plus2'和'sqrt（9）'。
這種想法是否正確？
不，這不太對。要理解FSA如何與計算相關，您需要採用更一般的計算視圖。
一般來說，計算是關於輸入和輸出的。現在，讓我們關注一種問題，我們可以計算答案：決策問題，輸出限制在「是」或「否」。讓我們進一步限制我們正在談論的那些問題類型，這些問題的輸入是字符串（比如「nice」）。這些正是FSA可以用來回答的問題（但他們無法回答所有這些問題！）。
因此，FSA可以回答（一些）以下形式的問題：字符串X是否擁有屬性Y？例如，「字符串是已知的有限字符串集合嗎？」，「字符串是奇數的二進制表示形式嗎？」，「字符串是否具有」貓「作爲子字符串？」。這些都可以由FSA來回答。
你的問題 - 像1 + 1 - 不是一個決定性問題。但是，您可以將其作爲決策問題，如下所示：「我的字符串是形式'x + y = z'，其中x，y和z是整數X，Y和Z的十進制表示形式，X + Y = Z ？」這個問題以及很多人喜歡的問題都不能用FSA來解決。
更強大的各種狀態機存在;他們不是「有限」的。例子包括下推自動機（PDA），線性有界自動機（LBA）和圖靈機（TM）。有一些決定問題的形式是「字符串X是否擁有財產Y？」即使是最強大的已知類型的自動機，圖靈機也不能回答。停止問題給出了一個例子：「給定'x（y）'，其中x是程序，y是程序的輸入，當X通過輸入y時，由X表示的程序停止嗎？」。在一般情況下，沒有TM - 也就是沒有算法 - 來回答這個問題。
你可以寫一個FSA來回答這個問題：「字符串x是否是我定義的這種語言的語法有效字符串？」當然，這取決於你的語言規則。 FSA可以識別「Number + Number + ... + Number」形式的字符串，但是FSA無法告訴您該金額是多少。但是，您不能爲此添加括號，否則FSA不再適用。換句話說，識別字符串和計算結果是有區別的，FSA通常被認爲是做前者。
請隨時提出任何其他問題。如果你有興趣在這些各種各樣的問題，請出示訪問以下站點，並承諾爲新的計算機科學StackExchange支持：
謝謝你的回答。據我所知，FSA已被證明可以作爲語言接受者（程序設計），那麼情況是否如此，但僅限於（非常）有限的情況？ – Neilos 2012-01-12 21:11:15
@Neilos：本質上，是的：有限狀態自動機識別常規語言，這是上下文無關語言的一個子集，它是上下文敏感語言的一個子集，它是圖靈機接受語言的一個子集，是字母表上所有可能語言集合的子集。隨着這些（如果適用）自動機越來越強大。實際計算（而不是決定）的想法最早從TMs，PDA開始（如果你想把結果留在堆棧中）......也許Moore/Mealy機器是有限的形式。 – Patrick87 2012-01-12 21:14:00
是否有這樣的事，作爲一個「嵌套FSA」？我的印象是（無界）嵌套導致無限的狀態。 – delnan 2012-01-12 20:54:39
那麼我的知識缺乏，嵌套FSA實際上可能更像是一個圖靈機，我只是想在FSA內運行子例程的方法，這可能是不可能的，但我真正的問題是如何能FSA充當編程語言接受者？我知道語言如何被接受，但他們是如何行事的，即當我打到狀態5時，我怎麼知道我有價值2以便能夠將它存儲在註冊表中或做我需要做的任何事情？在我看來，以任何方式擴展它不再是FSA。 – Neilos 2012-01-12 21:02:36
爲了計算A + B = C需要的不僅僅是一個有限狀態自動機，出於簡單的原因，語言a^n b^m c（n + m）不是一個常規語言，而是由抽象引理。 – Patrick87 2012-01-12 21:09:31