CS253 Theory of Computation

Laboratory topics are investigated using the JFLAP software tool. JFLAP was developed at Duke University by Susan Rogers and supports construction and testing of abstract machines and languages. Programming projects are implemented in C++. Example project topics include: deciding whether an NFA accepts some string w, conversion of an NFA to a DFA, conversion of an NFA to a CFG, and conversion of a CFG to Chomsky Normal Form.


L-Systems Lab
These images were rendered with JFLAP and the grammars are modifications of examples presented in the "Algorithmic Beauty of Plants" by P. Prusinkiewicz and A. Lindenmayer.

3D Bush Axioms

Start axiom, A;
A --> @@ [ & F L ! A ] / / / / / # [ & F L ! A ] / / / / / / / # [ & F L ! A ];
F --> S / / / / / F g;
L --> [ ^ ^ { - g + g + g - % - g + g + g } ];
S --> F L;
 
3D Flower Axioms

Start axiom, P;
F --> F g;
FL --> [ & & & PE / W / / / / W / / / / W / / / / W / / / / W ];
I --> F g S [ / / & & L ] [ / / ^ ^ L ] F g S;
L --> [ polygonColor=darkOliveGreen { + g - g g - g + % + g - g g - g } ];
P --> I + [ P + FL ] - - / / [ - - L ] I [ + + L ] - [ P FL ] + + P FL;
PE --> F g F g;
S --> F g F g;
W --> [ ^ F g ] [ polygonColor=orangeRed { & & & & - g + g % - g + g } ];
   

Students develop an original Lindenmayer System Grammar and use the JFLAP tool to graphically render a 2D or 3D image of the grammar. For a brief introduction to Lindenmayer Systems see the following resources:

  1. http://www.biologie.uni-hamburg.de/b-online/e28_3/lsys.html - An Introduction to L-Systems

  2. http://parallel.hpc.unsw.edu.au/complex/tutorials/tutorial2.html - Another Introduction to L-Systems using FractINT

  3. http://www.ee.uwa.edu.au/~braunl/lgrammar/java/ - An online Java Applet to generate L-Systems

  4. http://www.biologie.uni-hamburg.de/b-online/lsystjava/LSys.html - Another online Java Applet to generate L-Systems

  5. http://www.cpsc.ucalgary.ca/Research/bmv/vmm/animations.html - Online animations of plant growth from Univ. Calgary

  6. http://www.geocities.com/Athens/Academy/8764/lmuse/lmuse.html - Extremely cool MIDI file generation from L-System grammars using LMUSe

  7. http://www.geocities.com/Athens/Academy/8764/lmuse/lmusej.html - Download page for LMUSe

Lindenmayer Systems Lab Results
Plant, Andrew Beaudette Tree, Mark Wellons 3D - Bush, Manoj Pageni
 

Denise D. Byrnes