Chapter 19. Meeting 19, Approaches: Grammars and L-Systems 19.1. Announcements • Sonic system draft due: 27 April • No class Tuesday, 20 April • Be sure to do reading for next class: Riskin, J. 2003. “The Defecating Duck, or, the Ambiguous Origins of Artificial Life.” Critical Inquiry 29(4): 599-633. 19.2. Quiz • 10 Minutes 19.3. String Rewriting Systems • Given an alphabet and rewrite (production) rules, transform strings • A wide variety of formalizations and approaches • Axel Thue: first systematic treatment • Noam Chomsky: applied concept of re-writing to syntax of natural languages 19.4. Formal Grammars • A set of rules for a formal language • Formal grammars can be generative or analytic • Generative grammars defined by • A finite set of nonterminal symbols (variables that can be replaced) • A finite set of terminal symbols (constants) • An axiom, or initial state • A finite set of production rules, replacing variables with variables or constants • Generative grammars are iterative 20619.5. Lindenmayer Systems • Based on 1968 work of Aristid Lindenmayer • Origins in model of a natural systems: “a theoretical framework for studying the development of simple multicellular organisms” • 1984: began use of using computer graphics for visualization of plan structures • L-systems: formal grammars where re-writing is parallel, not sequential: all symbols are simultaneously replaced Image: Public domain (Wikipedia)YouTube (http://www.youtube.com/watch?v=L54SE9KTMSQ) YouTube (http://www.youtube.com/watch?v=t-FZhw9G-RQ) YouTube (http://www.youtube.com/watch?v=t-FZhw9G-RQ) • Motivation from natural systems: idea of cell divisions of occurring at the same time • L-systems can take many different forms depending on rule systems and alphabet components 20719.6. Context-Free • Rules match one source to one or more destination • Example: • Originally proposed by Lindenmayer to model growth of algae • Graphic representation Prusinkiewicz and Lindenmayer (1990) 208 Courtesy of Stelios Manousakis. Used with permission. From "Musical L-Systems." Master's Thesis, Royal Conservatory, The Hague, 2006.19.7. Context-Sensitive • Rules match two or more sources to one or more destination • 1L systems: match left or right of target source • 2L systems: match left and right of target source • 1L systems can be considered 2L systems with an empty (open matching) context • Example: 209 Figure 1.3: Example of a derivation in a DOL-system.© P. Prusinkiewicz and A. Lindenmayer (from The Algorithmic Beauty of Plants).All rights reserved. This content is excluded from our Creative Commons license.For more information, see http://ocw.mit.edu/fairuse.19.8. Non-Deterministic and Table L-systems • A context-sensitive or context free grammar can be deterministic • If the application of rules if probabilistic, non-deterministic grammar is created • Common approach: map one source to two or more destinations, with weighted probabilities for each destination • Example: 210 Courtesy of Stelios Manousakis. Used with permission. From "Musical L-Systems." Master's Thesis, Royal Conservatory, The Hague, 2006.• Alternatively, rules can be changed during production, producing a Table L-system (Manousakis 2006, p. 29) 211 Courtesy of Stelios Manousakis. Used with permission. From "Musical L-Systems." Master's Thesis, Royal Conservatory, The Hague, 2006.• Example: 19.9. Non-Propagative L-systems • Where rules replace source with more than one successor, the system grows and is propagative • If rules only encode one-value destinations, the rule system is non-propagative 212 Courtesy of Stelios Manousakis. Used with permission. From "Musical L-Systems." Master's Thesis, Royal Conservatory, The Hague, 2006.• Context-sensitive non-propagative L-systems are identical to a standard 1D CA • Example: 19.10. Musical and Artistic Application of L-systems • First published implementation: Prusinkiewicz Prusinkiewicz, P. 1986. “Score Generation with L-Systems.” In Proceedings of the International Computer Music Conference. San Francisco: International Computer Music Association. 455-457. • A spatial mapping of 2D graphical output of L-system curves to pitch (vertical) and duration (horizontal) 213 Courtesy of Stelios Manousakis. Used with permission. From "Musical L-Systems." Master's Thesis, Royal Conservatory, The Hague, 2006.• States determine intervals, not absolute values • Suggest application to other parameters: tempo, amplitude, and position of sound in space • Creative applications in the visual arts and architecture Stiny, G. and J. Gips. 1972. “Shape Grammars and the Generative Specification of Painting and Sculpture.” In Information Processing 71. C. V. Freiman, ed. Amsterdam: North Holland. 1460-1465. Internet: http://www.shapegrammar.org/ifip/. 214 Courtesy of Stelios Manousakis. Used with permission. From "Musical L-Systems." Master's Thesis, Royal Conservatory, The Hague, 2006.Courtesy of George Stiny. Used with permission.19.11. Reading: Mason and Saffle • Mason, S. and M. Saffle. 1994. “L-Systems, Melodies and Musical Structure.” Leonardo Music Journal 4: 31-38. • Are deterministic CA always fractal? • The basic mapping (after Prusinkiewicz) 215© MIT Press. All rights reserved. This content is excluded from our CreativeCommons license. For more information, see http://ocw.mit.edu/fairuse.Source: Mason, S. and M. Saffle. "L-Systems, Melodies and Musical Structure."Leonardo Music Journal 4 (1994): 31-38.216• What are some alternative ways the 2D turtle graphics can be mapped and as musical values? • Is it significant that “any melody can be modeled with an L-system, including the songs of aboriginal hunters, the plainchants of the medieval christian liturgy, the themes of beethoven’s symphonies and popular song tunes,” as the authors claim? • What is the implied connection between fractals and beauty. Is this connection sufficiently supported? 19.12. A Grammar Specification String and Python Implementation • Define a grammar in two required parts: alphabet and rules Both are specified in key{value} pairs Rules are specified as source{destination} pairs a{3}b{-2} @ a{b} b{a} • Optionally include the axiom (one chosen at random otherwise) a{3}b{-2} @ a{b} b{a} @ baba • Permit one to many rules of any size a{3}b{-2} @ a{ba} b{abb} @