article

A visual and interactive automata theory course emphasizing breadth of automata

Author:

Rakesh M. VermaAuthors Info & Claims

ACM SIGCSE Bulletin, Volume 37, Issue 3

Pages 325 - 329

https://doi.org/10.1145/1151954.1067535

Published: 27 June 2005 Publication History

Abstract

Teaching Theory of Computation and learning it are both challenging tasks. Moreover, students are not sufficiently interested/motivated to learn this material since: (i) they believe that the material is dated and of little use and (ii) it is too abstract and difficult. To counter the first perception, we have developed materials to illustrate the breadth of finite automata concepts. To overcome the second problem we have: enhanced and integrated visualization software and historical background into newly-devloped materials including homeworks and slides for lectures. Most of the materials are available at a web site for the course that we developed. Our preliminary experience is positive overall, but there are some remaining concerns.

References

[1]

Jon Barwise and John Etchemendy. uring's world 3.0. {CSLI} lecture notes no. 35. {CSLI} publications. echnical report, Stanford University, 1993.]]

[2]

Jon Barwise and John Etchemendy. Computers, visualization and the nature of reasoning. In T.W. Bynum and James H. Moor, editors, The Digital Phoenix: How Computers are Changing Philosophy}, pages 93--116. London: Blackwell, 1998.]]

[3]

R. Cavalcante, T. Finley, and S.H. Rodger. A visual and interactive theory course with jflap 4.0. In ACM SIGCSE '04}, pages 140--144, 2004.]]

Digital Library

[4]

Carlos I. Chesñevar, María Laura Cobo, and William Yurcik. Using Theoretical Computer Simulators for Formal Languages and Automata Theory. ACM SIGCSE Bulletin, 35(2):33--37, 2003.]]

Digital Library

[5]

C. I. Chesnevar, M. P. Gonzalez, and A. G. Maguitman. Didactic strategies for promoting significant learning in formal languages and automata theory. In ACM ITiCSE '04, pages 7--11, 2004.]]

Digital Library

[6]

H. Comon, M. Dauchet, R. Gilleron, et al. Tree Automata Techniques and Applications. Available on the Web, 1999.]]

[7]

M. Dauchet. Simulation of turing machines by a regular rewrite rule. Theoretical Computer Science}, 103:409--420, 1992. Also in RTA 1989.]]

Digital Library

[8]

N. Dershowitz and D. Plaisted. Rewriting. In J. A. Robinson and A. Voronkov, editors, Handbook of Automated Reasoning, volume 1, chapter 9, pages 535--610. Elsevier Science, 2001.]]

[9]

A collection of Links to Finite State Machine software. http://www.csd.uwo.ca/research/grail/links.html.]]

[10]

Eric Gramond and Susan Rodger. Using JFLAP to interact with theorems in automata theory. ACM SIGCSE Bulletin, 31(1):336--340, 1999.]]

Digital Library

[11]

M. T. Grinder. Animating automata: A cross platform program for teaching automata. In ACM SIGCSE '02, pages 63--67, 2002.]]

Digital Library

[12]

M. T. Grinder. A preliminary empirical evaluation of the effectiveness of a finite state automaton animator. In ACM SIGCSE '03, pages 157--161, 2003.]]

Digital Library

[13]

M.T. Grinder, S.B. Kim, T.L. Lutey, et al. Loving to learn theory: Active learning modules for the theory of computing. In ACM SIGCSE '02, pages 371--375, 2002.]]

Digital Library

[14]

M. Hamada and K. Shiina. A classroom experiment for teaching automata. In ACM ITiCSE '04, pages 261--261, 2004.]]

Digital Library

[15]

O. Hazzan. Reducing abstraction level when learning computability theory concepts. In ACM ITiCSE '02, pages 156--160, 2002.]]

Digital Library

[16]

C. D. Hundhausen, S. A. Douglas, and J. T. Stasko. A meta-study of algorithm visualization effectiveness. Journal of Visual Languages and Computing, 13(3):259--290, 2002.]]

[17]

Ted Hung and Susan Rodger. Increasing visualization and interaction in the automata theory course. In ACM SIGCSE '00, pages 6--10, 2000.]]

Digital Library

[18]

H. R. Lewis and C. H. Papadimitriou. Elements of the theory of Computation. Prentice Hall, 1998.]]

Digital Library

[19]

M. Murata. "Hedge Automata: a Formal Model for XML Schemata". Web page, 1999. citeseer.nj.nec.com/murata99hedge.html.]]

[20]

T. Naps, G. Rossling, et al. Exploring the role of visualization and engagement in computer science education. {R}eport of the Working Group on improving the educational impact of algorithm visualization. In ITICSE, 2002.]]

Digital Library

[21]

M. Robinson, J. Hamshar, J. Novillo, and A. Duchowski. A Java-based tool for reasoning about models of computation through simulating finite automata and turing machines. In ACM SIGCSE '99, 1999.]]

Digital Library

[22]

Susan Rodger, A. Bilska, K. Leider, et al. A collection of tools for making automata theory and formal languages come alive. ACM SIGCSE Bulletin, 29(1):15--19, 1997.]]

Digital Library

[23]

M. Sipser. Introduction to the Theory of Computation. PWS Publishing Co., 1997.]]

Digital Library

[24]

M. Vardi. Nontraditional applications of automata theory. In Theoretical Aspects of Computer Software, 1994.]]

Digital Library

[25]

Rakesh M. Verma and Shalitha A. Senanayake. LR2: A laboratory for rapid term graph rewriting. In Proc. Conf. on Rewriting Techniques & Applications, pages 252--255, 1999.]]

Digital Library

[26]

R. Wilhelm and D. Maurer. Compiler Design. Addison Wesley, 1997.]]

Digital Library

Cited By

Hundeshagen NLange M(2022)A Proposal for a Framework to Accompany Formal Methods Learning ToolsFormal Methods Teaching10.1007/978-3-030-91550-6_3(35-42)Online publication date: 1-Jan-2022
https://doi.org/10.1007/978-3-030-91550-6_3
Jovanović NMiljković DStamenković SJovanović ZChakraborty P(2020)Teaching concepts related to finite automata using ComVisComputer Applications in Engineering Education10.1002/cae.2235329:5(994-1006)Online publication date: 19-Oct-2020
https://doi.org/10.1002/cae.22353
Tecson CRodrigo M(2018)Tutoring Environment for Automata and the Users' Achievement Goal Orientations2018 IEEE International Conference on Teaching, Assessment, and Learning for Engineering (TALE)10.1109/TALE.2018.8615234(526-533)Online publication date: Dec-2018
https://doi.org/10.1109/TALE.2018.8615234
Show More Cited By

Index Terms

A visual and interactive automata theory course emphasizing breadth of automata
1. Social and professional topics
  1. Professional topics
    1. Computing education
      1. Computing education programs
        Computer science education
        Information science education
2. Software and its engineering
  1. Software notations and tools
    1. Context specific languages
      1. Visual languages

Recommendations

A visual and interactive automata theory course emphasizing breadth of automata
ITiCSE '05: Proceedings of the 10th annual SIGCSE conference on Innovation and technology in computer science education

Teaching Theory of Computation and learning it are both challenging tasks. Moreover, students are not sufficiently interested/motivated to learn this material since: (i) they believe that the material is dated and of little use and (ii) it is too ...
Weak Muller acceptance conditions for tree automata

Over the last decades the theory of automata on infinite objects has been an important source of tools for the specification and the verification of computer programs. Trees are more suitable than words to model nondeterminism and concurrency. In the ...
Converting two-way nondeterministic unary automata into simpler automata

We show that, on inputs of length exceeding 5n2, any n-state unary two-way nondeterministic finite automaton (2nfa) can be simulated by a (2n+2)-state quasi-sweeping 2nfa. Such a result, besides providing a “normal form” for 2nfa's, enables us to get a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGCSE Bulletin

ACM SIGCSE Bulletin Volume 37, Issue 3

September 2005

418 pages

ISSN:0097-8418

DOI:10.1145/1151954

Issue’s Table of Contents

ITiCSE '05: Proceedings of the 10th annual SIGCSE conference on Innovation and technology in computer science education
June 2005
440 pages
ISBN:1595930248
DOI:10.1145/1067445
Conference Chairs:
José Cunha
Universidade Nova de Lisboa, Portugal
,
William Fleischman
Villanova University
,
Program Chairs:
Viera K. Proulx
Northeastern University
,
João Lourenço
Universidade Nova de Lisboa, Portugal

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 June 2005

Published in SIGCSE Volume 37, Issue 3

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

39
Total Citations
View Citations
552
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)1

Reflects downloads up to 29 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hundeshagen NLange M(2022)A Proposal for a Framework to Accompany Formal Methods Learning ToolsFormal Methods Teaching10.1007/978-3-030-91550-6_3(35-42)Online publication date: 1-Jan-2022
https://doi.org/10.1007/978-3-030-91550-6_3
Jovanović NMiljković DStamenković SJovanović ZChakraborty P(2020)Teaching concepts related to finite automata using ComVisComputer Applications in Engineering Education10.1002/cae.2235329:5(994-1006)Online publication date: 19-Oct-2020
https://doi.org/10.1002/cae.22353
Tecson CRodrigo M(2018)Tutoring Environment for Automata and the Users' Achievement Goal Orientations2018 IEEE International Conference on Teaching, Assessment, and Learning for Engineering (TALE)10.1109/TALE.2018.8615234(526-533)Online publication date: Dec-2018
https://doi.org/10.1109/TALE.2018.8615234
Ade-Ibijola A(2018)Synthesis of regular expression problems and solutionsInternational Journal of Computers and Applications10.1080/1206212X.2018.148239842:8(748-764)Online publication date: 28-Jun-2018
https://doi.org/10.1080/1206212X.2018.1482398
Eickholt J(2015)Adding computing theory to a course on computer design and architectureJournal of Computing Sciences in Colleges10.5555/2752981.275300530:5(93-99)Online publication date: 1-May-2015
https://dl.acm.org/doi/10.5555/2752981.2753005
Hunt JMcGregor J(2009)A practical state machine projectProceedings of the 47th annual ACM Southeast Conference10.1145/1566445.1566500(1-6)Online publication date: 19-Mar-2009
https://dl.acm.org/doi/10.1145/1566445.1566500
Yu WVerma RWainwright RHaddad H(2008)Visualization of rule-based programmingProceedings of the 2008 ACM symposium on Applied computing10.1145/1363686.1363976(1258-1259)Online publication date: 16-Mar-2008
https://dl.acm.org/doi/10.1145/1363686.1363976
Frede CKnobelsdorf MMalmi LKorhonen AMcCartney RPetersen AMalmi LMcCartney R(2018)Exploring how Students Perform in a Theory of Computation Course using Final Exam and Homework Assignments DataProceedings of the 2018 ACM Conference on International Computing Education Research10.1145/3230977.3230996(241-249)Online publication date: 8-Aug-2018
https://dl.acm.org/doi/10.1145/3230977.3230996
Knobelsdorf MFrede CSheard JTenenberg JChinn DDorn B(2016)Analyzing Student Practices in Theory of Computation in Light of Distributed Cognition TheoryProceedings of the 2016 ACM Conference on International Computing Education Research10.1145/2960310.2960331(73-81)Online publication date: 25-Aug-2016
https://dl.acm.org/doi/10.1145/2960310.2960331
Decker ASimkins D(2016)Uncovering difficulties in learning for the intermediate programmer2016 IEEE Frontiers in Education Conference (FIE)10.1109/FIE.2016.7757446(1-8)Online publication date: Oct-2016
https://doi.org/10.1109/FIE.2016.7757446
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents