CFG를 사용하여 곱하기

Question

아래의 기능과 동일한 CFG를 만들려고합니다. 나는 B가 루프 카운터이므로 스택에 푸시 된 일련의 요소 일 수 있으므로 루프가 완료 될 때마다 B의 요소가 팝되고 B가 엡실론을 종료합니다. 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

CSG로 확실히 할 수는 있지만 CFG로는 불가능합니다. 펌핑 보조 정리는 불가능을 증명하기에 충분해야합니다. b이 고정

경우, 그러나, 그것은 쉽게 :

유일한 의미는 내가하는 CFG 구현할 수있는 생각할 수있는 형태

 
0a1a·b 

의 문자열을 인식

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

곱셈.