Introducing Finite Automata in Basic Education: A Work-in-Progress Proposal
Resumo
This paper presents a proposal for an educational activity to introduce finite automata in Basic Education through a narrative-based approach grounded in Project-Based Learning. Aiming to bridge the gap between Theoretical Computer Science and early school levels, the proposal consists of seven sequential missions where students take on the role of cyber defense agents. Each mission introduces core finite automata concepts – such as states, transitions, acceptance or rejection of a word, and language recognition – using progressive challenges that encourage problem solving and student autonomy.
Palavras-chave:
Computing Education, Automata Theory, Active Learning, K-12 Education
Referências
Barrows, H. S. (1996). Problem-based learning in medicine and beyond: A brief overview. New Directions for Teaching and Learning, 1996(68):3–12. DOI: 10.1002/tl.37219966804
Battal, A., Afacan Adanır, G., and Gülbahar, Y. (2021). Computer Science Unplugged: A Systematic Literature Review. Journal of Educational Technology Systems, 50(1):24–47. DOI: 10.1177/00472395211018801
Berbel, N. A. N. (2011). As metodologias ativas e a promoção da autonomia de estudantes. Semina: Ciências Sociais e Humanas, 32(1):25–40. DOI: 10.5433/1679-0383.2011v32n1p25
Brazil (2022). Computação: Complemento à BNCC. Disponível em: [link]. Accessed: Jun. 18, 2025.
Ching, Y.-H. and Hsu, Y.-C. (2024). Educational Robotics for Developing Computational Thinking in Young Learners: A Systematic Review. TechTrends, 68(3):423–434. DOI: 10.1007/s11528-023-00841-1
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. IEEE. DOI: 10.1109/HCC.2001.995251
Hopcroft, J. E., Motwani, R., and Ullman, J. D. (2001). Introduction to Automata Theory, Languages, and Computation. ACM Sigact News, 32(1):60–65. DOI: 10.1145/568438.568455
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 Transactions on Computing Education (TOCE), 17(1):1–28. DOI: 10.1145/2940331
Kiesmüller, 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. DOI: 10.1145/1594399.1594402
Kite, V., Park, S., and Wiebe, E. (2021). The Code-Centric Nature of Computational Thinking Education: A Review of Trends and Issues in Computational Thinking Education Research. Sage Open, 11(2):21582440211016418. DOI: 10.1177/21582440211016418
Mogensen, T. Æ. (2024). Introduction to Compiler Design. Springer Nature. DOI: 10.1007/978-3-031-46460-7
Ramos, M. V. M. (2009). Ensino de linguagens formais e autômatos em cursos superiores de computação. Revista de Computação e Tecnologia (ReCeT), 1(1):22–34.
Reeve, J. (2009). Why Teachers Adopt a Controlling Motivating Style Toward Students and How They Can Become More Autonomy Supportive. Educational Psychologist, 44(3):159–175. DOI: 10.1080/00461520903028990
Resnick, M. (2017). Lifelong Kindergarten: Cultivating Creativity Through Projects, Passion, Peers, and Play. MIT press.
Resnick, M., Maloney, J., Monroy-Hernández, A., Rusk, N., Eastmond, E., Brennan, K., Millner, A., Rosenbaum, E., Silver, J., Silverman, B., et al. (2009). Scratch: Programming for All. Communications of the ACM, 52(11):60–67. DOI: 10.1145/1592761.1592779
Silva, J. V., Silva Junior, B. A., Cavalheiro, S. A. C., and Foss, L. (2024). Exploring Automata Theory with an Educational Activity Using Graph Grammar for K-12 Education. In Simpósio Brasileiro de Informática na Educação (SBIE), pages 329–342. SBC. DOI: 10.5753/sbie.2024.242502
UNESCO Institute for Statistics (2012). International Standard Classification of Education: ISCED 2011. Technical report, UNESCO Institute for Statistics, Montreal, Canada. Accessed: Jul. 11, 2025.
Battal, A., Afacan Adanır, G., and Gülbahar, Y. (2021). Computer Science Unplugged: A Systematic Literature Review. Journal of Educational Technology Systems, 50(1):24–47. DOI: 10.1177/00472395211018801
Berbel, N. A. N. (2011). As metodologias ativas e a promoção da autonomia de estudantes. Semina: Ciências Sociais e Humanas, 32(1):25–40. DOI: 10.5433/1679-0383.2011v32n1p25
Brazil (2022). Computação: Complemento à BNCC. Disponível em: [link]. Accessed: Jun. 18, 2025.
Ching, Y.-H. and Hsu, Y.-C. (2024). Educational Robotics for Developing Computational Thinking in Young Learners: A Systematic Review. TechTrends, 68(3):423–434. DOI: 10.1007/s11528-023-00841-1
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. IEEE. DOI: 10.1109/HCC.2001.995251
Hopcroft, J. E., Motwani, R., and Ullman, J. D. (2001). Introduction to Automata Theory, Languages, and Computation. ACM Sigact News, 32(1):60–65. DOI: 10.1145/568438.568455
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 Transactions on Computing Education (TOCE), 17(1):1–28. DOI: 10.1145/2940331
Kiesmüller, 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. DOI: 10.1145/1594399.1594402
Kite, V., Park, S., and Wiebe, E. (2021). The Code-Centric Nature of Computational Thinking Education: A Review of Trends and Issues in Computational Thinking Education Research. Sage Open, 11(2):21582440211016418. DOI: 10.1177/21582440211016418
Mogensen, T. Æ. (2024). Introduction to Compiler Design. Springer Nature. DOI: 10.1007/978-3-031-46460-7
Ramos, M. V. M. (2009). Ensino de linguagens formais e autômatos em cursos superiores de computação. Revista de Computação e Tecnologia (ReCeT), 1(1):22–34.
Reeve, J. (2009). Why Teachers Adopt a Controlling Motivating Style Toward Students and How They Can Become More Autonomy Supportive. Educational Psychologist, 44(3):159–175. DOI: 10.1080/00461520903028990
Resnick, M. (2017). Lifelong Kindergarten: Cultivating Creativity Through Projects, Passion, Peers, and Play. MIT press.
Resnick, M., Maloney, J., Monroy-Hernández, A., Rusk, N., Eastmond, E., Brennan, K., Millner, A., Rosenbaum, E., Silver, J., Silverman, B., et al. (2009). Scratch: Programming for All. Communications of the ACM, 52(11):60–67. DOI: 10.1145/1592761.1592779
Silva, J. V., Silva Junior, B. A., Cavalheiro, S. A. C., and Foss, L. (2024). Exploring Automata Theory with an Educational Activity Using Graph Grammar for K-12 Education. In Simpósio Brasileiro de Informática na Educação (SBIE), pages 329–342. SBC. DOI: 10.5753/sbie.2024.242502
UNESCO Institute for Statistics (2012). International Standard Classification of Education: ISCED 2011. Technical report, UNESCO Institute for Statistics, Montreal, Canada. Accessed: Jul. 11, 2025.
Publicado
10/09/2025
Como Citar
VEIGA, Júlia; CAVALHEIRO, Simone André da Costa; FOSS, Luciana.
Introducing Finite Automata in Basic Education: A Work-in-Progress Proposal. In: WORKSHOP-ESCOLA DE INFORMÁTICA TEÓRICA (WEIT), 8. , 2025, Ponta Grossa/PR.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2025
.
p. 190-195.
