擴展到CFG，它是什麼？

考慮以下對允許規則在非終端右側有一個（或多個）終端的上下文無關語法的擴展。也就是說，形式的規則：擴展到CFG，它是什麼？

A b -> ...

右手邊可以是任何東西，像在上下文無關文法。特別是，需要而不是，右側末尾將具有完全相同的終端符號。在這種情況下，這個擴展會對上下文敏感。但終端不僅僅是一個上下文。有時候，這個終端被稱爲「回推」。

顯然，這不再是CFG（類型2）。它包括類型1。但是它是什麼？真的已經輸入0了嗎？

在Prolog的確定子句語法dcg中允許使用此特定擴展。（爲了避免誤解，我在這裏不考慮Prolog的完全擴展，即我假設終端來自有限字母表，並且不是任意的術語，也不認爲Prolog的額外參數在DCG中是允許的， 0的話）

編輯：這是描述擴展一個簡單的方法：添加到窗體的CFG規則

A b -> <epsilon>

來源

2012-08-22 false

您如何知道推回對應於A b - > ...規則？爲什麼不b A - > ...？ –

@CookieMonster：這就是Colmerauer的形式主義。 – false

不是必需的，尤其是沒有任何參考資料。這也可能是一件麻煩的事情。 –

回答我關於序言的DCG形式主義問題，這個擴展現在被稱爲一個semicontext。看看N253 DIN Draft for DCGs 2014-04-08 - ISO/IEC WDTR 13211-3:2014-04-08

鑑於

a1, [b] --> ... . 

a2, [b,b] --> ... .

終端序列[b]現在是一個semicontext，以及終端序列[b,b]。

會在同一終端序列現在出現在統治的結束，我們將有一個背景：

a3, [b,b] --> ..., [b,b].

因此，「半」是指這裏的「半壁江山」 - 類似於半羣，其中代數的一半集團持有的財產。

來源

2014-06-12 12:08:50 false

燁它的類型0我想。前3種類型（3,2和1）的原則是那些不能執行減少。這些只是生成型的。

在這裏，你可以將一個終端到的ε-所以它的類型0

來源

2012-08-22 16:36:11 m09

這裏的一個局部的答案：

語法是0型內的context-sensitive grammar （類型1）具有如下形式的規則wAx -> wBx其中w和x是終端和非終端的串，而B不是空的。請注意，因爲B不是空的，所以|wAx| <= |wBx|。你的語法的規則形式爲Ax -> z，其中z是一個終端和非終端的字符串，可以是空的，x可以被刪除。這違反了CSG的兩個原則。

Unsatisfyingly，我沒有回答兩件事情：

是由你的語法類型-1產生的語言？語法是類型0，但這並不意味着語言不能是類型1。例如，常規語言（類型3）可以由CFG描述（類型2）。
語言recursive？這很重要，因爲如果是這樣的話，語言是可判定的（不會受到停止問題的影響）。

我目前正在嘗試第二點的證明，但它可能超出我的能力。

來源

2012-08-22 16:44:03 DPenner1

在您的文章中的小錯字，可能應該閱讀| wAx | <= | wBx |？ –

謝謝，再次更新......我不應該用小睡眠來做正式語法，太容易出錯。 – DPenner1

擴展到CFG，它是什麼？

回答

相關問題