确定语言是否上下文无关 [英] Determine if a language is context free

问题描述

让我们说您有一种语言L，并且您想确定它是否与上下文无关.与常规语言相交的上下文无关语言是上下文无关的.足以证明L是上下文无关的吗?

Lets say you have a language L and you want to determine if it is context free. Context free languages intersected with regular languages are context free. Is that enough to prove that L is context free?

含义

L相交P = T其中P是常规语言，T是上下文无关的.这是否意味着L是上下文无关的?

L intersect P = T Where P is a regular language and T is context free. Does this imply that L is context free?

推荐答案

否，您的声明不是是.请考虑以下反例:

No, your statement is not true. Consider the following counter-example:

L = {0n1n2n | n > 0}, P = T = Ø.显然，我们有L ∩ P = L ∩ Ø = Ø = T，而Ø既是常规的又是上下文无关的.

L = {0n1n2n | n > 0}, P = T = Ø. Clearly we have L ∩ P = L ∩ Ø = Ø = T, and Ø is both regular and context-free.

请注意，众所周知L不是上下文无关的(

Note it is well-known that L is not context-free (see example on p.12 for a sketch proof by pumping lemma).

这篇关于确定语言是否上下文无关的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！