這是一種上下文無關或語境敏感的語言嗎？

Question

我正在學習正式語言和自動機理論，並且我對書中沒有回答的問題有疑問。問題是：

這種語言上下文無關，常規或上下文相關？

L = {A^I B ^ĴC 1-4 K |我< = j的或j < = I，J = K}

Answer 1

這是上下文敏感的。

不規律：我們必須記住有限狀態機不能的b或c的出現次數。

沒有上下文自由，就好像我們應用抽象引理，你會看到我們有更多的B比C的推後b像字符串a^{2}b^{2} b^{n-4}b^{2}c^{n}。

所以它是上下文敏感的。

Answer 2

它是上下文無關的。它可與以下CFG指定：

S -> AX 
A -> aA 
A -> epsilon 
X -> bXc 
X -> epsilon 

，因爲你需要A狀態下接受盡可能多的a秒。 X產生等量的b和c。因此，此CFG指定語言L.