Visualization of Automata

Pradip Peter Dey et al

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.

 
  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 Turing Machines:

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 Pushdown Automata (PDA):


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 PDA:

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.
 
Static Visualization of a PDA

Dynamic Visualization of Finite Automata (FA):


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:

A Finite Automaton for ab*


Please provide your comments Automata Visualization

You are requested to fill out every field; however, a partially filled out form is also accepted. That is, every field is optional.

- - - - - - - - - -
 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - -
 
First Name
Middle Name
Last Name
Email Address
Are you a student? (Yes/No plus comments)
Are Automata easy to learn with visualization? (Yes/No/Not Sure plus comments)
Do visualized examples help in learning the concepts? (Yes/No/Not Sure plus comments)
Are you likely to study more about automata? (Yes/No/Not Sure plus comments)
Any other comments?


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.
Tversky, B., Morrison, J. B., & Betrancourt, M. (2002). Animation: can it facilitate?. International Journal of Human–Computer Studies, 57, 247–262.

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.

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