我們如何編寫上下文無關語言的程序？程序是否應該用遞歸可枚舉的語言來完成圖靈？

Question

如果我們主要使用上下文無關的語言進行編碼，我真的無法理解我們如何模擬圖靈機（它接受遞歸可枚舉語言）的輸出。

Answer 1

您正在混淆程序的規格和輸出。

例如，可以接受遞歸可枚舉語言的圖靈機仍然由有限轉換函數或「規則表」指定。規則表本身可以用常規語言表達。

再次，只有現代編程語言的基本語法完全由上下文無關語法定義。一個有效的程序必須滿足很多條件，這些條件不能被語法捕獲：標識符必須在使用之前聲明，函數只能定義一次，程序必須通過類型檢查器等等。

Answer 2

「大部分上下文無關」與「略懷孕」沒有意義的方式沒有任何意義。該屬性要麼存在，要麼不存在，並且對於我曾經使用過的任何編程語言，它都不是。

但這不是你可以在其中編寫任意算法的原因。語言的源代碼語法可能會或可能不會被特定的語法描述，但重要的是輸入/輸出行爲。例如，打印形式爲A^iB^iC^i的字符串的程序可以用Pascal編寫，即使這些字符串不構成上下文無關語言。但是這可能的原因並不在於Pascal語法強於上下文無關（雖然的確如此），而是Pascal中構造的語義（最終，程序將運行的馮諾依曼機器的概念）。