Bad news: not context free

Let the developers know what you think of the software and what can be done to either improve the CFDG language or the Context Free program.

Moderators: MtnViewJohn, chris, mtnviewmark

Post Reply
User avatar
kipling
Posts: 91
Joined: Wed Jun 18, 2008 2:36 am

Bad news: not context free

Post 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]
	}

User avatar
MtnViewJohn
Site Admin
Posts: 882
Joined: Fri May 06, 2005 2:26 pm
Location: Mountain View, California
Contact:

Re: Bad news: not context free

Post 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.

Post Reply