Automata Theory in Computing Education: A Systematic Review
Resumo
This paper presents a systematic literature review investigating approaches to teaching Automata Theory in Computing Education. Automata Theory, a foundational area of Computer Science essential for understanding formal languages and compilers, is increasingly recognized for its importance in educational contexts. This study examines how Automata Theory is approached, assessed, integrated, and taught in both higher education and K-12 settings. The review reveals several innovative and traditional methods used to enhance student engagement and comprehension, including educational tools and games. However, the findings highlight a lack of standardized assessment methods in current practices, as well as a gap in approaches in the K-12 context.
Palavras-chave:
Automata Theory, Computing Education, Teaching Methodologies
Referências
Bezáková, I., Fluet, K., Hemaspaandra, E., Miller, H., and Narváez, D. E. (2022). Effective Succinct Feedback for Intro CS Theory: A JFLAP Extension. In Proceedings of the 53rd ACM Technical Symposium on Computer Science Education - Volume 1, SIGCSE 2022, page 976–982, New York, NY, USA. Association for Computing Machinery.
Brazil (2022). Normas sobre Computação na Educação Básica. [link]. Online. Accessed on March 2024.
Budiselic, I., Srbljic, S., and Popovic, M. (2007). RegExpert: A Tool for Visualization of Regular Expressions. In EUROCON 2007 - The International Conference on “Computer as a Tool”, pages 2387–2389.
Castro-Schez, J. J., del Castillo, E., Hortolano, J., and Rodriguez, A. (2009). Designing and Using Software Tools for Educational Purposes: FLAT, a Case Study. IEEE Transactions on Education, 52(1):66–74.
Cavalcante, R., Finley, T., and Rodger, S. H. (2004). A Visual and Interactive Automata Theory Course with JFLAP 4.0. In Proceedings of the 35th SIGCSE Technical Symposium on Computer Science Education, pages 140–144.
Chakraborty, P., Saxena, P. C., and Katti, C. P. (2011). Fifty Years of Automata Simulation: A Review. ACM Inroads, 2(4):59–70.
Chesnevar, C. I., González, M. P., and Maguitman, A. G. (2004). Didactic Strategies for Promoting Significant Learning in Formal Languages and Automata Theory. ACM SIGCSE Bulletin, 36(3):7–11.
Cogliati, J. J., Goosey, F. W., Grinder, M. T., Pascoe, B. A., ROSS, R. J., and Williams, C. J. (2005). Realizing the Promise of Visualization in the Theory of Computing. J. Educ. Resour. Comput., 5(2):5–es.
Cogumbreiro, T. and Blike, G. (2022). Gidayu: Visualizing Automaton and Their Computations. In Proceedings of the 27th ACM Conference on on Innovation and Technology in Computer Science Education Vol. 1, ITiCSE ’22, page 110–116, New York, NY, USA. Association for Computing Machinery.
Coppin, C. A., Mahavier, W. T., May, E. L., and Parker, E. (2009). The Moore Method: A Pathway to Learner-Centered Instruction. Number 75. MAA.
del Vado Vírseda, R. (2020). From the Mathematical Impossibility Results of the High School Curriculum to Theoretical Computer Science. In Proceedings of the 20th Koli Calling International Conference on Computing Education Research, pages 1–5.
Dengel, A. (2018). Seeking the Treasures of Theoretical Computer Science Education: Towards Educational Virtual Reality for the Visualization of Finite State Machines. In 2018 IEEE International Conference on Teaching, Assessment, and Learning for Engineering (TALE), pages 1107–1112.
Dengel, A. (2020). How Important is Immersion for Learning in Computer Science Replugged Games? In Proceedings of the 51st ACM Technical Symposium on Computer Science Education, SIGCSE ’20, page 1165–1171, New York, NY, USA. Association for Computing Machinery.
Dershowitz, N. and Dowek, G. (2016). Universality in Two Dimensions. Journal of Logic and Computation, 26(1):143–167.
DeVellis, R. F. (2003). Scale Development: Theory and Applications. Sage London, 13:0–176.
Dey, P. P., Sinha, B. R., and Amin, M. (2020). Supporting Asynchronous Learners with Multiple Representations. Journal of Computing Sciences in Colleges, 36(2):108–116.
Gramond, E. and Rodger, S. H. (1999). Using JFLAP to Interact with Theorems in Automata Theory. In The Proceedings of the Thirtieth SIGCSE Technical Symposium on Computer Science Education, pages 336–340.
Grinder, M. T. (2002). Animating Automata: A Cross-Platform Program for Teaching Finite Automata. In Proceedings of the 33rd SIGCSE Technical Symposium on Computer Science Education, pages 63–67.
Grinder, M. T. (2003). A Preliminary Empirical Evaluation of the Effectiveness of a Finite State Automaton Animator. ACM Sigcse Bulletin, 35(1):157–161.
Habiballa, H. and Kmet’, T. (2004). Theoretical Branches in Teaching Computer Science. International Journal of Mathematical Education in Science and Technology, 35(6):829–841.
Hartmann, W., Nievergelt, J., and Reichert, R. (2001). Kara, Finite State Machines, and the Case for Programming as Part of General Education. In Proceedings IEEE Symposia on Human-Centric Computing Languages and Environments (Cat. No.01TH8587), pages 135–141.
Holly, M., Tscherko, J.-H., and Pirker, J. (2022). An Interactive Chess-Puzzle-Simulation for Computer Science Education. In 2022 8th International Conference of the Immersive Learning Research Network (iLRN), pages 1–5.
Honda, F., Pires, F., Pessoa, M., and Oliveira, E. (2023). Automigos: Learning Design para Ludificação de Autômatos Finitos Determinísticos. In Anais do XXXI Workshop sobre Educação em Computação, pages 545–556, Porto Alegre, RS, Brasil. SBC.
Hopcroft, J. E., Motwani, R., and Ullman, J. D. (2001). Introduction to Automata Theory, Languages, and Computation. ACM Sigact News, 32(1):60–65.
Hopcroft, J. E. and Ullman, J. D. (1969). Formal Languages and their Relation to Automata. Addison-Wesley Longman Publishing Co., Inc., USA.
Hung, T. and Rodger, S. H. (2000). Increasing Visualization and Interaction in the Automata Theory Course. ACM SIGCSE Bulletin, 32(1):6–10.
Isayama, D., Ishiyama, M., Relator, R., and Yamazaki, K. (2016). Computer Science Education for Primary and Lower Secondary School Students: Teaching the Concept of Automata. ACM Trans. Comput. Educ., 17(1).
Jovanovic, N., Miljkovic, D., Stamenkovic, S., Jovanovic, Z., and Chakraborty, P. (2021). Teaching Concepts Related to Finite Automata Using ComVis. Computer Applications in Engineering Education, 29(5):994–1006.
Kiesmuller, U. (2009). Diagnosing Learners’ Problem-solving Strategies Using Learning Environments with Algorithmic Problems in Secondary Education. ACM Transactions on Computing Education (TOCE), 9(3):1–26.
Kitchenham, B. (2004). Procedures for Performing Systematic Reviews. Keele, UK, Keele University, 33(2004):1–26.
Knobelsdorf, M., Kreitz, C., and Bohne, S. (2014). Teaching Theoretical Computer Science Using a Cognitive Apprenticeship Approach. In Proceedings of the 45th ACM Technical Symposium on Computer Science Education, pages 67–72.
Korte, L., Anderson, S., Pain, H., and Good, J. (2007). Learning by Game-Building: A Novel Approach to Theoretical Computer Science Education. In Proceedings of the 12th Annual SIGCSE Conference on Innovation and Technology in Computer Science Education, pages 53–57.
Maurer, P. M. (2021). Computer Science Theory from a Practical Point of View. In 2021 International Conference on Computational Science and Computational Intelligence (CSCI), pages 920–924.
McDonald, J. (2002). Interactive Pushdown Automata Animation. In Proceedings of the 33rd SIGCSE Technical Symposium on Computer Science Education, pages 376–380.
Mogensen, T. Æ. (2024). Introduction to Compiler Design. Springer Nature.
Mohammed, M., Shaffer, C. A., and Rodger, S. H. (2021). Teaching Formal Languages with Visualizations and Auto-Graded Exercises. In Proceedings of the 52nd ACM Technical Symposium on Computer Science Education, SIGCSE ’21, page 569–575, New York, NY, USA. Association for Computing Machinery.
Neto, J. and Terra, R. (2016). LFApp: Um Aplicativo Móvel para o Ensino de Linguagens Formais e Autômatos. In Anais do XXIV Workshop sobre Educação em Computação, pages 2196–2205, Porto Alegre, RS, Brasil. SBC.
Page, M. J., McKenzie, J. E., Bossuyt, P. M., Boutron, I., Hoffmann, T. C., Mulrow, C. D., Shamseer, L., Tetzlaff, J. M., Akl, E. A., Brennan, S. E., et al. (2021). The PRISMA 2020 Statement: An Updated Guideline for Reporting Systematic Reviews. Bmj, 372.
Petri, G., von Wangenheim, C. G., and Borgatto, A. F. (2016). MEEGA+: An Evolution of a Model for the Evaluation of Educational Games. INCoD/GQS, 3:1–40.
Procopiuc, M., Procopiuc, O., and Rodger, S. H. (1996). Visualization and Interaction in the Computer Science Formal Languages Course with JFLAP. In Technology-Based ReEngineering Engineering Education Proceedings of Frontiers in Education FIE’96 26th Annual Conference, volume 1, pages 121–125. IEEE.
Robinson, M. B., Hamshar, J. A., Novillo, J. E., and Duchowski, A. T. (1999). A Java-based Tool for Reasoning About Models of Computation Through Simulating Finite Automata and Turing Machines. In The Proceedings of the Thirtieth SIGCSE Technical Symposium on Computer Science Education, pages 105–109.
Rodger, S. H., Bilska, A. O., Leider, K. H., Procopiuc, M., Procopiuc, O., Salemme, J. R., and Tsang, E. (1997). A Collection of Tools for Making Automata Theory and Formal Languages Come Alive. In Proceedings of the Twenty-Eighth SIGCSE Technical Symposium on Computer Science Education, pages 15–19.
Vieira, L. F. M., Vieira, M. A. M., and Vieira, N. J. (2004). Language Emulator, a Helpful Toolkit in the Learning Process of Computer Theory. ACM Sigcse Bulletin, 36(1):135–139.
Wagenknecht, C. and Friedman, P. D. (1998). Teaching Nondeterministic and Universal Automata Using Scheme. Computer Science Education, 8(3):197–227.
Brazil (2022). Normas sobre Computação na Educação Básica. [link]. Online. Accessed on March 2024.
Budiselic, I., Srbljic, S., and Popovic, M. (2007). RegExpert: A Tool for Visualization of Regular Expressions. In EUROCON 2007 - The International Conference on “Computer as a Tool”, pages 2387–2389.
Castro-Schez, J. J., del Castillo, E., Hortolano, J., and Rodriguez, A. (2009). Designing and Using Software Tools for Educational Purposes: FLAT, a Case Study. IEEE Transactions on Education, 52(1):66–74.
Cavalcante, R., Finley, T., and Rodger, S. H. (2004). A Visual and Interactive Automata Theory Course with JFLAP 4.0. In Proceedings of the 35th SIGCSE Technical Symposium on Computer Science Education, pages 140–144.
Chakraborty, P., Saxena, P. C., and Katti, C. P. (2011). Fifty Years of Automata Simulation: A Review. ACM Inroads, 2(4):59–70.
Chesnevar, C. I., González, M. P., and Maguitman, A. G. (2004). Didactic Strategies for Promoting Significant Learning in Formal Languages and Automata Theory. ACM SIGCSE Bulletin, 36(3):7–11.
Cogliati, J. J., Goosey, F. W., Grinder, M. T., Pascoe, B. A., ROSS, R. J., and Williams, C. J. (2005). Realizing the Promise of Visualization in the Theory of Computing. J. Educ. Resour. Comput., 5(2):5–es.
Cogumbreiro, T. and Blike, G. (2022). Gidayu: Visualizing Automaton and Their Computations. In Proceedings of the 27th ACM Conference on on Innovation and Technology in Computer Science Education Vol. 1, ITiCSE ’22, page 110–116, New York, NY, USA. Association for Computing Machinery.
Coppin, C. A., Mahavier, W. T., May, E. L., and Parker, E. (2009). The Moore Method: A Pathway to Learner-Centered Instruction. Number 75. MAA.
del Vado Vírseda, R. (2020). From the Mathematical Impossibility Results of the High School Curriculum to Theoretical Computer Science. In Proceedings of the 20th Koli Calling International Conference on Computing Education Research, pages 1–5.
Dengel, A. (2018). Seeking the Treasures of Theoretical Computer Science Education: Towards Educational Virtual Reality for the Visualization of Finite State Machines. In 2018 IEEE International Conference on Teaching, Assessment, and Learning for Engineering (TALE), pages 1107–1112.
Dengel, A. (2020). How Important is Immersion for Learning in Computer Science Replugged Games? In Proceedings of the 51st ACM Technical Symposium on Computer Science Education, SIGCSE ’20, page 1165–1171, New York, NY, USA. Association for Computing Machinery.
Dershowitz, N. and Dowek, G. (2016). Universality in Two Dimensions. Journal of Logic and Computation, 26(1):143–167.
DeVellis, R. F. (2003). Scale Development: Theory and Applications. Sage London, 13:0–176.
Dey, P. P., Sinha, B. R., and Amin, M. (2020). Supporting Asynchronous Learners with Multiple Representations. Journal of Computing Sciences in Colleges, 36(2):108–116.
Gramond, E. and Rodger, S. H. (1999). Using JFLAP to Interact with Theorems in Automata Theory. In The Proceedings of the Thirtieth SIGCSE Technical Symposium on Computer Science Education, pages 336–340.
Grinder, M. T. (2002). Animating Automata: A Cross-Platform Program for Teaching Finite Automata. In Proceedings of the 33rd SIGCSE Technical Symposium on Computer Science Education, pages 63–67.
Grinder, M. T. (2003). A Preliminary Empirical Evaluation of the Effectiveness of a Finite State Automaton Animator. ACM Sigcse Bulletin, 35(1):157–161.
Habiballa, H. and Kmet’, T. (2004). Theoretical Branches in Teaching Computer Science. International Journal of Mathematical Education in Science and Technology, 35(6):829–841.
Hartmann, W., Nievergelt, J., and Reichert, R. (2001). Kara, Finite State Machines, and the Case for Programming as Part of General Education. In Proceedings IEEE Symposia on Human-Centric Computing Languages and Environments (Cat. No.01TH8587), pages 135–141.
Holly, M., Tscherko, J.-H., and Pirker, J. (2022). An Interactive Chess-Puzzle-Simulation for Computer Science Education. In 2022 8th International Conference of the Immersive Learning Research Network (iLRN), pages 1–5.
Honda, F., Pires, F., Pessoa, M., and Oliveira, E. (2023). Automigos: Learning Design para Ludificação de Autômatos Finitos Determinísticos. In Anais do XXXI Workshop sobre Educação em Computação, pages 545–556, Porto Alegre, RS, Brasil. SBC.
Hopcroft, J. E., Motwani, R., and Ullman, J. D. (2001). Introduction to Automata Theory, Languages, and Computation. ACM Sigact News, 32(1):60–65.
Hopcroft, J. E. and Ullman, J. D. (1969). Formal Languages and their Relation to Automata. Addison-Wesley Longman Publishing Co., Inc., USA.
Hung, T. and Rodger, S. H. (2000). Increasing Visualization and Interaction in the Automata Theory Course. ACM SIGCSE Bulletin, 32(1):6–10.
Isayama, D., Ishiyama, M., Relator, R., and Yamazaki, K. (2016). Computer Science Education for Primary and Lower Secondary School Students: Teaching the Concept of Automata. ACM Trans. Comput. Educ., 17(1).
Jovanovic, N., Miljkovic, D., Stamenkovic, S., Jovanovic, Z., and Chakraborty, P. (2021). Teaching Concepts Related to Finite Automata Using ComVis. Computer Applications in Engineering Education, 29(5):994–1006.
Kiesmuller, U. (2009). Diagnosing Learners’ Problem-solving Strategies Using Learning Environments with Algorithmic Problems in Secondary Education. ACM Transactions on Computing Education (TOCE), 9(3):1–26.
Kitchenham, B. (2004). Procedures for Performing Systematic Reviews. Keele, UK, Keele University, 33(2004):1–26.
Knobelsdorf, M., Kreitz, C., and Bohne, S. (2014). Teaching Theoretical Computer Science Using a Cognitive Apprenticeship Approach. In Proceedings of the 45th ACM Technical Symposium on Computer Science Education, pages 67–72.
Korte, L., Anderson, S., Pain, H., and Good, J. (2007). Learning by Game-Building: A Novel Approach to Theoretical Computer Science Education. In Proceedings of the 12th Annual SIGCSE Conference on Innovation and Technology in Computer Science Education, pages 53–57.
Maurer, P. M. (2021). Computer Science Theory from a Practical Point of View. In 2021 International Conference on Computational Science and Computational Intelligence (CSCI), pages 920–924.
McDonald, J. (2002). Interactive Pushdown Automata Animation. In Proceedings of the 33rd SIGCSE Technical Symposium on Computer Science Education, pages 376–380.
Mogensen, T. Æ. (2024). Introduction to Compiler Design. Springer Nature.
Mohammed, M., Shaffer, C. A., and Rodger, S. H. (2021). Teaching Formal Languages with Visualizations and Auto-Graded Exercises. In Proceedings of the 52nd ACM Technical Symposium on Computer Science Education, SIGCSE ’21, page 569–575, New York, NY, USA. Association for Computing Machinery.
Neto, J. and Terra, R. (2016). LFApp: Um Aplicativo Móvel para o Ensino de Linguagens Formais e Autômatos. In Anais do XXIV Workshop sobre Educação em Computação, pages 2196–2205, Porto Alegre, RS, Brasil. SBC.
Page, M. J., McKenzie, J. E., Bossuyt, P. M., Boutron, I., Hoffmann, T. C., Mulrow, C. D., Shamseer, L., Tetzlaff, J. M., Akl, E. A., Brennan, S. E., et al. (2021). The PRISMA 2020 Statement: An Updated Guideline for Reporting Systematic Reviews. Bmj, 372.
Petri, G., von Wangenheim, C. G., and Borgatto, A. F. (2016). MEEGA+: An Evolution of a Model for the Evaluation of Educational Games. INCoD/GQS, 3:1–40.
Procopiuc, M., Procopiuc, O., and Rodger, S. H. (1996). Visualization and Interaction in the Computer Science Formal Languages Course with JFLAP. In Technology-Based ReEngineering Engineering Education Proceedings of Frontiers in Education FIE’96 26th Annual Conference, volume 1, pages 121–125. IEEE.
Robinson, M. B., Hamshar, J. A., Novillo, J. E., and Duchowski, A. T. (1999). A Java-based Tool for Reasoning About Models of Computation Through Simulating Finite Automata and Turing Machines. In The Proceedings of the Thirtieth SIGCSE Technical Symposium on Computer Science Education, pages 105–109.
Rodger, S. H., Bilska, A. O., Leider, K. H., Procopiuc, M., Procopiuc, O., Salemme, J. R., and Tsang, E. (1997). A Collection of Tools for Making Automata Theory and Formal Languages Come Alive. In Proceedings of the Twenty-Eighth SIGCSE Technical Symposium on Computer Science Education, pages 15–19.
Vieira, L. F. M., Vieira, M. A. M., and Vieira, N. J. (2004). Language Emulator, a Helpful Toolkit in the Learning Process of Computer Theory. ACM Sigcse Bulletin, 36(1):135–139.
Wagenknecht, C. and Friedman, P. D. (1998). Teaching Nondeterministic and Universal Automata Using Scheme. Computer Science Education, 8(3):197–227.
Publicado
04/11/2024
Como Citar
SILVA, Júlia Veiga da; CAVALHEIRO, Simone André da Costa; FOSS, Luciana.
Automata Theory in Computing Education: A Systematic Review. In: SIMPÓSIO BRASILEIRO DE INFORMÁTICA NA EDUCAÇÃO (SBIE), 35. , 2024, Rio de Janeiro/RJ.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2024
.
p. 301-313.
DOI: https://doi.org/10.5753/sbie.2024.242472.
