這是什麼語法？上下文無關的或上下文敏感的

我學習形式語言與自動機理論，我有一個關於未在它回答裏面的書有問題的問題。問題是：這是什麼語法？上下文無關的或上下文敏感的

這是語言語境免費，定期或上下文敏感？

L = {A ^Ñ瓦特瓦特^{- [R} b ^Ñ | w是（A + B）*，W ^{- [R}是瓦特反向且n> = 0}

我認爲這種語言是上下文相關的，因爲它需要至少兩個堆疊用於接受。

上，可能有人對此有何評論？

謝謝。

來源

2013-04-08 Bardya Momeni

爲什麼你認爲它需要兩個堆棧？你確定他們不能合併成一個單一的堆棧嗎？ – ibid 2013-04-08 14:08:51

@ibid：一個堆棧推它裏面一個的保存到的數量，一個堆棧節省W，然後彈出在W元素，使其扭轉，然後與第一組的每個流行，我們把B的末來匹配a的數量。你看，你不能將a和w合併到同一個棧中，並知道W或R（W）何時完成。所以我們需要兩個堆棧。可以評論？ – 2013-04-08 14:21:46

我看到已經有，使點我正在:-)答案 – ibid 2013-04-09 08:33:36

語言^ň瓦特W¯¯^[R b ^ñ是上下文無關語言。我們可以爲這種語言編寫上下文無關的語法。

S --> aSb | R 
R --> aRa | bRb |^

^是空符號

PDA：對語言有^Ñ瓦特瓦特^{- [R} b ^Ñ

推前綴字符串aⁿ
推w
流行w而在w^R
彈出所有a在後綴bⁿ

注意，在堆棧和比賽推向b對陣符號中的每個符號：我們在處理字符串語言^ñ WW ^{- [R} b的^ñ通過PDA，我們不知道在哪裏前綴aⁿ結束又在哪裏w前w^R開始所以對於這種語言，我們不能得出一個deterministic model of PDA although Non-deterministic PDA is possible結束。而重要的是非確定性PDA類與確定性PDA類不同，意思是scope deterministic context free languages are not equals to non-deterministic context free.（實際上確定性是非確定性CFL的子集）

來源

2013-04-08 17:49:04

*讓我知道我的回答可以幫助或者你需要更多的細節* – 2013-04-08 17:53:24

這是一個有點混亂，我的意思是，即使在NPDA，我們不能知道當W完成停止彈出並開始分析堆棧內容以獲得b後綴。例如，你有AAA AAB咩BBB，你推AAA，AAB那麼，現在流行的b - AA - [現在我們無法知道停止爆裂，或開始把B的 - 感謝 – 2013-04-08 20:50:04

假設我們有AA bbaab baabb BB ，堆棧操作放（A，A，b，b，A，A，b），然後彈出這樣開始：如果棧頂等於輸入然後彈出去下一個輸入和重複，否則，如果堆棧的頂部是不等於輸入，彈出堆棧並放入b，直到堆棧爲空......所以，這可以被一個堆棧接受。 – 2013-04-08 21:49:28

這是什麼語法？上下文無關的或上下文敏感的

回答

相關問題