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;

Answer 1

CFG では確かにそれを行うことができますが、CFG ではそれを行うことはできません。ポンピング補題は、不可能性を証明するのに十分なはずです。

bただし、 が修正された場合は簡単です。

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

それはフォームの文字列を認識します

0 a 1 a・b

これは、CFG が乗算を実装できると私が考えることができる唯一の意味です。