Page 1 of 1

Bad news: not context free

Posted: Thu Aug 02, 2012 5:33 pm
by kipling
After my last "purity" design in the gallery I figured out that I could convince CF3 to do things it shouldn't be able to do.

Unless you argue that there are only 2^32 possible values for n here and so all I have done is defined a very large finite context free grammar. But in this case you may as well say that everything is a finite state machine.

I think this means that the "Impure" criterion for parameters will have be rethought.

Code: Select all

/*
	A set of CF3 rules to generate the language
	{XYZ, XXYYZZ, XXXYYYZZZ, ...}
*/
	
startshape S
//CF::Impure=1
shape S{ X(0)[a -.3] }

shape X(natural n)
	rule 10{
		CIRCLE[sat 1 b 1]
		X(n+1)[x 1  r -5..5]
		arrow[ b -1 a 1 x .3]
		}
	rule 1{
		CIRCLE[sat 1 b 1]
		arrow[ r -90 b -1 a 1 y -.3]
		Y(n+1,n+1)[ y -1 r 190]
		}



shape Y(natural n,natural m){
	if (n>0){
		SQUARE[r 45 sat 1 b .8 h 120]
		Y(n--1,m)[x 1 r -5..5]
		if (n>1) arrow[ b -1 a 1 x .3]
		else arrow[ r 90 b -1 a 1  y .3]
		}
	else {
		Z(m)[x -1 y 1 r 170]
		}
	}

shape Z(natural n) {
	if (n>0){
		TRIANGLE[sat 1 b 1 h 240]
		Z(n--1)[x 1  r -5..5]
		if (n>1) arrow[ b -1 a 1 x .3]
		}
	}


shape arrow{
	SQUARE[[s .25 .15 x .5 z 99]]
	TRIANGLE[s .3 r -90 x .3 z 99]
	}

Re: Bad news: not context free

Posted: Fri Aug 03, 2012 12:29 pm
by MtnViewJohn
Yes, I make exactly this argument. If Context Free 2.2 were capable of handling billions of rules then you could translate this grammar to Context Free 2.2. The natural parameters let you declare a finite sized family of rules. The upper limit of the size of this family is 2^51 per parameter. Your Y shape has about 2^101 members. I admit that this is ridiculously large.

Maybe we could reduce the upper bound to something reasonable, like 1000. There could be a CF::MaxNatural variable that you could set if you wanted a higher limit.