3 ms·
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 t
by YeGoblynQueenne 3y ago
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.
- kragen 3y agoyou 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!
- YeGoblynQueenne 3y agoUgh, 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!
- kragen 3y agosorry! you don't owe me any work but if you have some notes somewhere I'd be delighted to read them. maybe email?