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 a Turing Machine forL_{1 }= { 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 L_{1 } = { 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

afollowed by any number ofb's (2) a^{n}b^{n}c^{n}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 ofa'sb's andc'sDynamic Visualization of a Turing Machine using a Java AppletThis Turing Machine accepts any string with equal number ofa'sb's anda's that is, a string with the pattern a^{n}b^{n}a^{n}, where n > 0.aabbaawill be accepted by this machine; butaabbaaaaawill not be accepted.Dynamic Visualization of a Turing Machine forL_{1 }= { 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 L_{1 } = { 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
L_{equal} = { a^{n}b^{n } : 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 L_{equal}. Dynamic visualization of a PDA can be seen following the link given below:

**
Animation of a Pushdown Automaton for L _{m } = { {^{n}c}^{n } : where n >=0 } **

Static Visualization of a PDA can be seen following the link given below where
a PDA for L_{m } = { {^{n}c}^{n } : where n >=0 } is demonstrated with an input.

Static Visualization of a PDA

Finite Automata (FA) accept Regular Languages, such as
L_{2} = 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.

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