加法验证程序...不是常规的，但是上下文无关吗？ [英] verifier of addition... not-regular, but is it context-free?

问题描述

如何证明以下语言是（不是）上下文无关的？

n b ^m c ^{{n + m}} | n，m> = 0}是上下文无关的。有关证明，请参见

http://cg.scs.carleton.ca/~michiel/TheoryOfComputation/TheoryOfComputation.pdf （pdf中为p102；文本中为p94）

证明很长，可以通过使用与PDA的等效性来证明它更短（例如，先在堆栈中将符号n +压入m次，然后再将其取下n +无论哪种方式，此示例都使我相信我的原始语言也必须与上下文无关。但是，我真的不知道如何为此辩护。

解决方案

否，您的假设是不正确的！

语言 L = {x = y + z |其中x，y，z是二进制整数，x是y和z的总和} 是 not 上下文无关语言（CFL）。

我尝试解释一下。

首先，请考虑以下示例字符串 s 用语言 L 。

  110 = 100 + 10 
 1110 = 1100 + 10 
：
 111000 = 110000 + 1000 
  

在我的解释中，LHS为 X 问题，RHS为 Y + Z 。

什么是抽引物？ CFL吗？

如果语言L是上下文无关的，则存在一些整数p≥1，这样L中的任何字符串s都带有| s |。 ≥p。 （其中p是泵送长度，可以写成

  s = uvxyz 
，其子字符串为u，v， x，y和z，使得
1。| vxy |≤p，
 2. | vy |≥1和
3。uv nxy nz对于每个自然数n均为L 。
  

此定义|≥1，并且
3. uv nxy nz在L中表示

注意： s 的中间部分， vxy 不大于抽水长度 p （条件1）

[解决方案] ：

让我们在<$ c $中选择字符串 s 满足条件 | s |≥p

我们的 s 是1 ^m 0 ^q = 1 ^m-1 0 ^q + 1 0 ^q ，其中 q> p，m-1> p

现在 s 的总长度为 2m + 2q -1 然后是 p ，当然还有一些自然数的组合可能会导致不等式（为了使说明简单，我不包括 + 和 = 的长度）

现在我们的 s 是语言，根据CFG的抽奖引理，足够大。

现在打破它：

u vxy z = 1 ^m 0 ^q = 1 ^m-1 0 ^q + 1 0 ^q

尝试找到 v 和 y 到泵并以语言L生成新字符串，但是请记住 v 和 y 不应比 p （根据条件1）。

v 和 y 以便您可以生成新的语言字符串！

（步骤1）：因为如果您选择增加 1 ，那么您不能同时泵送 = 的RHS和LHS，因为LHS的最后 1 在 q （> p）到RHS的前 1 。因此不可能生成新的语言字符串。

（步骤2）：：假设您想再次泵出 0 可能会在LHS和RHS上同时增加 0 ，因为m-1（> p）中LHS的最后 0 扩展为RHS上的前 0 。

（步骤3）：：您不能组合 111 ... 000 ... 双方。 ，请尝试使用此语言，您将获得语言L之外的字符串。

也可以在Pumping Lemma规则内尝试其他选项。您将找不到 v 和 y 的正确选择。

[ANSWER]

所以他有一个字符串 s 足够大，使用它我们无法生成新的语言字符串。它与CFL的Pumping Lemma矛盾，因此给定 L 不是CFL。

How can I show that the following language is (not) context-free? The argument that it's not regular goes as follows.

I suspect this language to be context-free... The reason why I think this, is because L = {aⁿ b^m c^{n+m} | n,m >= 0} is context-free. A proof for this can be found at

http://cg.scs.carleton.ca/~michiel/TheoryOfComputation/TheoryOfComputation.pdf (p102 in pdf; p94 in text)

The proof is kind of long and it can probably be proven much shorter by making use of the equivalence with PDAs (i.e. pushing first some symbol n "+" m times on the stack, and consequently taking it off again n+m times.) Either way, this example makes me believe that my original language must also be context-free. Yet, I don't really see how I can argue for this.

解决方案

No, your assumption is not correct!

The language L = { x = y + z | where x, y, z are binary integers and x is the sum of y and z} is not Context Free Languages(CFL).

I try to explain.

First of all, consider following examples strings s in language L.

110 = 100 + 10   
1110 = 1100 + 10  
:
111000 = 110000 + 1000    

In my explanation LHS is X in question and RHS is Y + Z.

What is pumping Lemma for CFL?
If a language L is context-free, then there exists some integer p ≥ 1 such that any string s in L with |s| ≥ p. (where p is a "pumping length" can be written as

s = uvxyz
with substrings u, v, x, y and z, such that
1. |vxy| ≤ p,
2. |vy| ≥ 1, and
3. uv nxy nz is in L for every natural number n.  

This definition | ≥ 1, and 3. uv nxy nz is in L for every natural number n.

Notice: Middle part of s , vxy not greater then pumping length p. (condition 1)

[SOLUTION]:

Let us choose a string s in L that satisfy condition |s| ≥ p

our s is 1^m0^q = 1^m-10^q + 10^q , where q > p , m-1 > p

Now total length of s is 2m + 2q -1 that is greater then p and of-course for some combination of natural numbers this inequality is possible (I am not including length of + and = to keep explanation simple )

Now our s is in language and sufficiently large according to pumping lemma for CFG.

Now break it:

u vxy z = 1^m0^q = 1^m-10^q + 10^q

Try to find v and y to pump and generate new string in language L, But keep in mind v and y should not be too much far than p (according to condition 1).

You don't have any choice for v and y such that you can generate new strings in language!

(Step-1): Because if you chose to increase 1 then you can't pump both side RHS and LHS of = because last 1 on LHS is at q (>p) to first 1 of RHS. hence not possible to generate new strings in language.

(Step-2): Suppose you like to pump 0 again its not possible to increase 0 on LHS and RHS together because last 0 on LHS in m-1 (>p) distend to first 0 on RHS.

(Step-3): You can't pump a combination of 111...000... both side. , try this you will get string out of language L.

Try other options too within the rules of Pumping Lemma. you would not find correct choice for v and y.

[ANSWER]

So he have a string s in L that is sufficiently large and using that we can't generate new strings in language. its contradict to Pumping Lemma for CFL hence given L is not a CFL.

这篇关于加法验证程序...不是常规的，但是上下文无关吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！