我在哪里可以找到线性上下文无关语言抽取引理的证明？
我正在寻找特定于线性上下文无关语言的证明
问问题
446 次
1 回答
1
我也找了正式的教授，但找不到。不确定下面是否是正式的教授，但它可能会给你一些想法。
引理：对于每一个线性上下文无关语言 L 都有一个 n>0，因此对于 L 中的每一个 w 和 |w| > n 我们可以把 w 写成 uvxyz 使得 |vy|> 0,|uvyz| <= n 和 uv^ixy^iz 对于每个 i>= 0 在 L 中。
“证明”：想象一棵 L 中带有开始符号 S 的长字符串 w 的解析树。还假设该树不包含无用节点。如果 w 足够长，将至少有一个非终结符重复不止一次。让我们称第一个沿树 X 向下的重复非终结符，它的第一次出现（从顶部）为 X[1]，第二次出现为 X[2]。令 x 为 w 中由 X[2] 生成的字符串， vxy 是由 X[1] 生成的字符串，uvxyz 是由 S 生成的完整字符串 w。由于从 X[1] 到 X[2] 的移动会生成 v,y，因此理论上我们可以生成一棵新树，并在其中多次复制此移动在从 X[1] 向下移动之前。这证明了每个 i>= 0 的 uv^ixy^iz 都在 L 中。由于我们的树不包含无用的节点，从 X[1] 移动到 X[2] 必须生成一些终端，这证明 |vy|> 0.L 是线性的，这意味着在树的每一层上我们都有一个非终端符号。树中的每个节点都覆盖了 w 中的某个子字符串，其长度受节点高度的线性函数限制。从 S 移动到 X[2] 涵盖了从 w 开始的 uv 和 yz，并且行进的树级别的数量以 (2 * 非终结符号的数量 + 1) 为界。由于行进的层数是有界的，并且树是线性的，因此它也对从 S 到 X[2] 的移动的产量施加了界限，这意味着 ,|uvyz| <= n 对于某些 n >= 0。从 S 移动到 X[2] 涵盖了从 w 开始的 uv 和 yz，并且行进的树级别的数量以 (2 * 非终结符号的数量 + 1) 为界。由于行进的层数是有界的，并且树是线性的，因此它也对从 S 到 X[2] 的移动的产量施加了界限，这意味着 ,|uvyz| <= n 对于某些 n >= 0。从 S 移动到 X[2] 涵盖了从 w 开始的 uv 和 yz，并且行进的树级别的数量以 (2 * 非终结符号的数量 + 1) 为界。由于行进的层数是有界的，并且树是线性的，因此它也对从 S 到 X[2] 的移动的产量施加了界限，这意味着 ,|uvyz| <= n 对于某些 n >= 0。
注意：请记住，我们构造 X[1] ， X[2] 自上而下，这与我们通常如何证明上下文无关语法的“常规”泵引理相矛盾。在“常规”泵浦引理中，X[1] 的高度有一个界限，因此 |vxy| 有一个界限。在我们的例子中，X[1] 的高度没有界限，它可以高达w 的长度所要求的。然而，从 S 到 X[2] 的树级别数有一个界限。如果语法不是线性的，因为输出从 S 到 X[2]，这并没有多大意义仍然只有 S 的高位有界（即无界）。但在线性情况下，此输出是有界的，因此 |uvyz| <= n
于 2019-03-18T00:37:11.323 回答