Some static and dynamic visualizations of automata (or mathematical models of computation) are linked to this page for considerations in teaching relations between automata and other fields of computer science. Static visualizations are often found in books and journals and therefore they are not emphasized here. The examples of dynamic visualizations or animations shown here are a part of an ongoing study about effectiveness
of dynamic visualizations in education. A thorough review of over 20 studies
(Tversky, Morrison, & Betrancourt, 2002) compared learning from static
and animated graphics and concluded that there was no advantage of
animations over static graphics. A small number of studies that showed some advantage,
apparently presented more information in the animated graphics
than in the static graphics (see also Lowe & Schnotz, 2007 and Larkin & Simon, 1987). The main goal of the current study is to enhance animations with additional information and learner centered interactions that cannot be presented in static graphics.
Dynamic Visualization of Turing Machines:
Logically speaking, the class of Turing Machines is the most powerful class of computing machines. Any problem that can be solved computationally can be solved by a Turing Machine. Thus, computability means Turing computability.
Dynamic visualization of Turing Machines can be seen following the links given below.
Static Visualization of a Turing Machine can be seen following the link given below where a Turing Machine for L1 = { aba* } = { ab, aba, abaa, abaaa, abaaaa, abaaaaa, . . . . } is demonstrated with an input.
Static Visualization of a Turing Machine
Dynamic Visualization of Turing Machines using Flash
After you follow this link, select one of the following two choices:
(1) ab*
If you select this choice, then type a string such as abbbb
in the white editable input field and then click on the
Process button. This machine accepts any string with one a
followed by any number of b's
(2) anbncn
If you select this choice, then type a string such as aabbcc
in the white editable input field and then click on the
Process button. This machine accepts any string with equal number of a's
b's and c's
Dynamic Visualization of a Turing Machine using a Java Applet
This Turing Machine accepts any string with equal number of a's
b's and a's that is, a string with the pattern anbnan,
where n > 0. aabbaa will be accepted by this machine; but aabbaaaaa
will not be accepted.
Dynamic Visualization of a Turing Machine for
L1 = { aba* } = { ab, aba, abaa, abaaa, abaaaa, abaaaaa, . . . . } is
demonstrated with an input. Compare this with the static visualization given below.
Static Visualization of a Turing Machine can be seen following the link given below where a Turing Machine for L1 = { aba* } = { ab, aba, abaa, abaaa, abaaaa, abaaaaa, . . . . } is demonstrated with an input.
Static Visualization of a Turing Machine
Pushdown Automata (PDA) accept Context-Free Languages, such as
Lequal = {   anbn   : where n >0 } = { ab, aabb, aaabbb, aaaabbbb, aaaaabbbbb, . . . . }. Every word or string in this language has equal number of a's and b's. PDA use a stack for matching equal number of a's and b's in Lequal. Dynamic visualization of a PDA can be seen following the link given below:
Animation of a Pushdown Automaton for Lm = { {nc}n : where n >=0 }
Static Visualization of a PDA can be seen following the link given below where
a PDA for Lm = { {nc}n : where n >=0 } is demonstrated with an input.
Finite Automata (FA) accept Regular Languages, such as
L2 = aba* = { ab, aba, abaa, abaaa, abaaaa, abaaaaa, . . . . }. Dynamic visualization of an FA can be seen following the link given below: You are requested to fill out every field; however, a partially filled out form is also accepted. That is, every field is optional.
Bibliography:
Cohen, D. (1997). Introduction to Computer Theory (2nd ed.), New York: John Wiley & Sons.
Hopcroft, J. E., Motwani, R. & Ullman, J. (2007). Introduction to Automata Theory,
Languages, and Computation. Pearson Education.
Kahneman, D. (2002). Maps of bounded rationality: A perspective on intuitive judgment and choice (Nobel Prize Lecture).
In Tore Fr�ngsmyr, (ed.). Les Prix Nobel. The Nobel Prizes 2002, 416-499, Retrieved March 12, 2009 from
http://nobelprize.org/nobel_prizes/economics/laureates/2002/kahneman-lecture.html
Lowe, R. K. & Schnotz, W. (Eds) (2007) Learning with animation, New York: Cambridge University Press.
Rich, E. ( 2007) Automata, Computability and Complexity: Theory and Applications
Rodger, S.H. (2006) Learning automata and formal languages interactively with JFLAP. ITiCSE 2006: 360
Rodger, S. H. & Finley, T. W. (2006). JFLAP: An Interactive Formal Languages and Automata Package. Jones & Bartlett Publishers.
Rodger, S.H., Bressler, B., Finley, T. & Reading, S. (2006). Turning automata theory into a
hands-on course. SIGCSE 2006: 379-383
Rodger, S.H., Eric Wiebe, Kyung Min Lee, Chris Morgan, Kareem Omar, Jonathan Su. (2009). Increasing
engagement in automata theory with JFLAP. SIGCSE 2009: 403-407
Sipser, M. (2006) Introduction to the Theory of Computation, PWS Publishing.
R. Gregory Taylor (1998) Models of Computation and Formal Languages, Oxford University Press.
Wong, A., Marcus, N., Paul Ayres, Lee Smith, Graham A. Cooper, Fred Paas and John Sweller (2009).
Instructional animations can be superior to statics when learning human motor skills, Computers
in Human Behavior, Volume 25, Issue 2, March 2009, Pages 339-34
Cyril Rebetez, Mireille B�trancourt, Mirweis Sangin and Pierre Dillenbourg (2009). Learning
from animation enabled by collaboration. Instructional Science.
Richard E. Mayer and Roxana Moreno.(2002). Animation as an Aid to Multimedia Learning, Educational
Psychology Review, Volume 14, Number 1
Tsay, Y., Chen, Y., Tsai, M., Wu, K. & Chan, W. (2007). GOAL: A Graphical Tool for
Manipulating B�chi Automata and Temporal Formulae, in Tools and Algorithms for the
Construction and Analysis of Systems. Springer.
Tversky, B., Morrison, J. B., & Betrancourt, M. (2002). Animation: can it facilitate?.
International Journal of Human�Computer Studies, 57, 247�262.
Dynamic Visualization of a Turing Machine for
L1 = { aba* } = { ab, aba, abaa, abaaa, abaaaa, abaaaaa, . . . . } is
demonstrated with an input. Compare this with the static visualization given below.
Static Visualization of Turing Machines:
 
Static Visualization of Turing Machines:
 
Dynamic Visualization of Pushdown Automata (PDA):
Static Visualization of PDA:
 
Static Visualization of a PDA
Dynamic Visualization of Finite Automata (FA):
Please provide your comments on Automata Visualization
Tversky, B., Morrison, J. B., & Betrancourt, M. (2002). Animation: can it facilitate?. International
Journal of Human�Computer Studies, 57, 247�262.
Finite Automata (FA) Related Programming assignments
Programming Assignment
For questions and comments, please contact:
Dr. Pradip Peter Dey,
Professor, School of Engineering and Technology
National University
3678 Aero Court, San Diego, CA 92123
U.S.A.
Phone: (858) 309-3421
Fax (858) 309-3420
Email: pdey@nu.edu