Search code examples
mathcontext-free-grammarcontext-free-language

Multiplying using a CFG

I am trying to make a CFG that is equivalent the function below. I know that B is the loop counter so it could be a series of elements pushed onto a stack, every time the loop is completed an element from B is popped and if B = Epsilon quit. How do I handle the addition in the top half of the while loop?

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;
Solution

  • You're not going to be able to do that with a CFG, although you could certainly do it with a CSG. The pumping lemma should suffice to prove impossibility.

    If b is fixed, though, it's easy:

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

    That will recognize strings of the form

    0a1a·b

    which is the only sense I can think of in which a CFG can implement multiplication.