语言 L = a^(2^k) 的上下文无关文法
Context-free grammar for language L = a^(2^k)
作为计算理论练习的一部分，我被要求为语言 L = a^(2^k) 找到一种上下文无关语言。
我是如何尝试解决它的：我想使用一个 X 句子，它递归地将其他句子产生的所有 a 加倍。这只会引导我找到像 a、a^2、a^4、a^8 这样的字符串，这是我正在寻找的语法。
但是这样的事情可能吗？我怎样才能做到这一点？
S -> aS | X | ε
Χ -> (doubles all previous a's)
还有一个问题是，将一串 as 加倍会产生许多 as 不被 a^(2^k) 条件接受，例如 a ^3、a^5、a^6 都属于 "in-between" a^(2^k) 的级数差距。
考虑您的语言中的字符串 a^(2^p)，其中 p 是上下文无关语言的抽取引理中的常量。我们可以将此字符串写成 uvxyz 这样：
|vy| >= 1|vxy| <= p
那么我们知道，如果语言是上下文无关的，那么所有 u v^n x y^n z 形式的字符串都应该在 n >= 0 的语言中。让我们调用 a = |uxz| 和 b = |vy|。那么我们必须有长度为a, a + b, a + 2b, ...的语言的字符串。假设a = 2^k是2的幂，a + b也是2的幂，那么b = 2^m - 2^k，a + 2b = 2^(m+1) - 2^k = 2^j也是2的幂，改写成[=24] =].除以 k 和 j 中的较小者得到 2^r = 2^s + 1。满足此方程的唯一方法是 s = 0，即 k = j，否则 RHS 为奇数而 LHS 必须为偶数。但随后 m = k 也和 b = 0。但是 b 必须大于 0，根据泵引理。
丑陋的男人，但你明白了。
作为计算理论练习的一部分，我被要求为语言 L = a^(2^k) 找到一种上下文无关语言。
我是如何尝试解决它的：我想使用一个 X 句子，它递归地将其他句子产生的所有 a 加倍。这只会引导我找到像 a、a^2、a^4、a^8 这样的字符串，这是我正在寻找的语法。
但是这样的事情可能吗？我怎样才能做到这一点？
S -> aS | X | ε
Χ -> (doubles all previous a's)
还有一个问题是，将一串 as 加倍会产生许多 as 不被 a^(2^k) 条件接受，例如 a ^3、a^5、a^6 都属于 "in-between" a^(2^k) 的级数差距。
考虑您的语言中的字符串 a^(2^p)，其中 p 是上下文无关语言的抽取引理中的常量。我们可以将此字符串写成 uvxyz 这样：
|vy| >= 1|vxy| <= p
那么我们知道，如果语言是上下文无关的，那么所有 u v^n x y^n z 形式的字符串都应该在 n >= 0 的语言中。让我们调用 a = |uxz| 和 b = |vy|。那么我们必须有长度为a, a + b, a + 2b, ...的语言的字符串。假设a = 2^k是2的幂，a + b也是2的幂，那么b = 2^m - 2^k，a + 2b = 2^(m+1) - 2^k = 2^j也是2的幂，改写成[=24] =].除以 k 和 j 中的较小者得到 2^r = 2^s + 1。满足此方程的唯一方法是 s = 0，即 k = j，否则 RHS 为奇数而 LHS 必须为偶数。但随后 m = k 也和 b = 0。但是 b 必须大于 0，根据泵引理。
丑陋的男人，但你明白了。