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: chris, MtnViewMark, MtnViewJohn

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

Bad news: not context free

Post by kipling » Thu Aug 02, 2012 5:33 pm

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
startshape S
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
Site Admin
Posts: 844
Joined: Fri May 06, 2005 2:26 pm
Location: Mountain View, California

Re: Bad news: not context free

Post by MtnViewJohn » Fri Aug 03, 2012 12:29 pm

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

Who is online

Users browsing this forum: No registered users and 3 guests