math - 使用 CFG 相乘

Question

我正在尝试制作一个与以下功能等效的 CFG。我知道 B 是循环计数器，因此它可能是推入堆栈的一系列元素，每次循环完成时，都会弹出 B 中的一个元素，并且如果 B = Epsilon 退出。如何处理 while 循环上半部分的加法？

PROCEDURE multiply a, b;
VAR a, b, z;
BEGIN
z := 0;
  WHILE b > 0 DO BEGIN
        z := a + z;
        b := b - 1;
  END
  RETURN z;
END;

score 0 · Accepted Answer

您将无法使用 CFG 做到这一点，尽管您当然可以使用 CSG 做到这一点。抽水引理应该足以证明不可能。

但是，如果b是固定的，这很容易：

S ⇒ ε
S ⇒ 0 S 1 1 … 1
       (b 次)

这将识别形式的字符串

0 ^a 1 ^a·b

这是我能想到的唯一一种 CFG 可以实现乘法的意义。

1 回答 1