Hacker News new | past | comments | ask | show | jobs | submit login

Lindemayer's book (The Algorithmic Beauty of Plants) claims L-systems are not CFGs because all expansions to a non-terminal are applied simultaneously, rather than sequentially. Having played around with simple l-systems, the claim holds some water. No time to go into details now but I can give some examples later if requested.



you get the same result if you apply them sequentially, don't you? to me the crucial difference is that you stop after a certain number of iterations, a number which is uniform across the whole string, so for interesting l-systems your final string has nonterminals in it, while usually with a cfg your terminals and nonterminals are disjoint and so you can't stop expanding until you run out of nonterminals

i'd love to see your examples!


Ugh, sorry. Too much work. Maybe I'll write about it somewhere (don't have a blog or anything) in which case I'll post it here. Sorry!


sorry! you don't owe me any work but if you have some notes somewhere I'd be delighted to read them. maybe email?




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: