Exploring Automata Theory with an Educational Activity Using Graph Grammar for K-12 Education

• Júlia Veiga da Silva Universidade Federal de Pelotas https://orcid.org/0000-0002-6839-3117
• Braz Araujo da Silva Junior Universidade Federal de Pelotas https://orcid.org/0000-0002-1637-5320
• Simoné André da Costa Cavalheiro Universidade Federal de Pelotas https://orcid.org/0000-0002-7442-7379
• Luciana Foss Universidade Federal de Pelotas https://orcid.org/0000-0002-0473-4111

DOI: https://doi.org/10.5753/sbie.2024.242502

Resumo

This paper proposes an educational activity for K-12 Education, aligned with the Brazilian National Common Curricular Base, which explores Automata Theory using Graph Grammar. Although several areas of computing are increasingly integrated into the educational context, the theoretical area is still neglected. Due to the scarcity of direct approaches in K-12 Education, this project seeks to bridge this gap. The proposed activity not only develops a specific National Common Curricular Base skill but also indirectly enhances Computational Thinking skills.

Referências

Barr, V. and Stephenson, C. (2011). Bringing Computational Thinking to K-12: What is Involved and What is the Role of the Computer Science Education Community? ACM Inroads, 2(1):48–54.

Brazil (2022). Normas sobre Computação na Educação Básica. [link]. Online. Accessed on March 2024.

Carvalho, F., Junior, M. C., and Costa, Y. (2021). Jogos Educativos no Ensino de Autômato Finito Determinístico: Um Estudo de Caso com o Jogo A Factory Disaster. In Anais Estendidos do XX Simpósio Brasileiro de Jogos e Entretenimento Digital, pages 472–478, Porto Alegre, RS, Brasil. SBC.

Cayetano-Jiménez, I. U., Martinez-Ríos, E. A., Bustamante-Bello, R., Ramírez-Mendoza, R., and Ramírez-Montoya, M. S. (2024). Experimenting with Soft Robotics in Education: A Systematic Literature Review from 2006 to 2022. IEEE Transactions on Learning Technologies, pages 1–18.

Chen, P., Yang, D., Metwally, A. H. S., Lavonen, J., and Wang, X. (2023). Fostering Computational Thinking Through Unplugged Activities: A Systematic Literature Review and Meta-Analysis. International Journal of STEM Education, 10(1):47.

Ching, Y.-H. and Hsu, Y.-C. (2023). Educational Robotics for Developing Computational Thinking in Young Learners: A Systematic Review. TechTrends, pages 1–12.

da Silva, J. V., Junior, B. S., Foss, L., and Cavalheiro, S. (2021). Adaptação do processo ENgAGED para o desenvolvimento de conteúdos curriculares em uma plataforma de jogos baseada em Gramática de Grafos. In Anais do XXXII Simpósio Brasileiro de Informática na Educação, pages 316–327, Porto Alegre, RS, Brasil. SBC.

Ehrig, H., Heckel, R., Korff, M., Lowe, M., Ribeiro, L., Wagner, A., and Corradini, A. (1997). Algebraic Approaches to Graph Transformation. Part II: Single Pushout Approach and Comparison with Double Pushout Approach. In Handbook of Graph Grammars and Computing by Graph Transformation. Volume 1: Foundations. World Scientific Publishing Co., Inc.

Farias, E., Lopes, P., Carvalho, W., and Porfírio, E. (2023). Análise da Adoção de Pensamento Computacional no Contexto Escolar Brasileiro: Um Mapeamento Sistemático da Literatura. In Anais do XXXIV Simpósio Brasileiro de Informática na Educação, pages 1625–1636, Porto Alegre, RS, Brasil. SBC.

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).

Junior, B. S., Cavalheiro, S., and Foss, L. (2021). GrameStation: Specifying games with graphs. In Anais do XXXII Simpósio Brasileiro de Informática na Educação, pages 499–511, Porto Alegre, RS, Brasil. SBC.

Lee, S. J. and Kwon, K. (2024). A Systematic Review of AI Education in k-12 classrooms from 2018 to 2023: Topics, Strategies, and Learning Outcomes. Computers and Education: Artificial Intelligence, 6:100211.

Leite, L., Sibaldo, M. A., de Carvalho, T., and de Souza, R. (2014). Montanha de Chomsky: Jogo Tutor para Auxílio no Ensino de Teoria da Computação. In Anais do XXII Workshop sobre Educação em Computação, pages 110–119, Porto Alegre, RS, Brasil. SBC.

Mogensen, T. Æ. (2024). Introduction to Compiler Design. Springer Nature.

Resnick, M. (2017). Lifelong Kindergarten: Cultivating Creativity Through Projects, Passion, Peers, and Play. MIT Press.

Sanusi, I. T., Oyelere, S. S., Vartiainen, H., Suhonen, J., and Tukiainen, M. (2023). A Systematic Review of Teaching and Learning Machine Learning in K-12 Education. Education and Information Technologies, 28(5):5967–5997

Silva, R. C., Binsfeld, R. L., Carelli, I. M., and Watanabe, R. (2010). Automata Defense 2.0: Reedição de um Jogo Educacional para Apoio em Linguagens Formais e Autômatos. In Brazilian Symposium on Computers in Education (Simpósio Brasileiro de Informática na Educação-SBIE), volume 1.

Silva Junior, B., Cavalheiro, S., and Foss, L. (2019). Revisitando um Jogo Educacional para Desenvolver o Pensamento Computacional com Gramática de Grafos. In Brazilian Symposium on Computers in Education (Simpósio Brasileiro de Informática na Educação-SBIE), volume 30, page 863.

Silva Junior, B., Cavalheiro, S., and Foss, L. (2021). Theoretical Computer Science in Basic Education: A Systematic Review. In Anais do VI Workshop-Escola de Informática Teórica, pages 133–140, Porto Alegre, RS, Brasil. SBC.

Silva Junior, B. A. d. (2020). GGasCT: Bringing Formal Methods to the Computational Thinking. Master’s thesis, Universidade Federal de Pelotas.

Tomizawa, M. and Junior, M. C. (2021). Automata Toy Factory: Um Jogo Educativo para Ensino de Autômato com Pilha. In Anais Estendidos do XX Simpósio Brasileiro de Jogos e Entretenimento Digital, pages 389–397, Porto Alegre, RS, Brasil. SBC.

Vieira, M. and Sarinho, V. (2019). Máquina de Senhas: Um Jogo Digital para o Aprendizado da Teoria dos Autômatos. In Anais da XIX Escola Regional de Computação Bahia, Alagoas e Sergipe, pages 54–59, Porto Alegre, RS, Brasil. SBC.

Wing, J. M. (2006). Computational Thinking. Communications of the ACM, 49(3):33–35.

Yim, I. H. Y. and Su, J. (2024). Artificial Intelligence (AI) Learning Tools in k-12 Education: A Scoping Review. Journal of Computers in Education, pages 1–39.