Course: Automata Theory
Class: Second Year (Sem-II)
Department: Computer Science and Information Technology
Author: Prof. Ashwini B. Patil
- Abstract:
The course on Finite Automata is significant in the curriculum of computer science engineering and information technology field because it serves as a prerequisite for the courses on system software and compiler design and because the ideas covered in this course have broad applications in computer science and other related engineering fields.
The aim of this course to study the abstract machines and automata, as well as the computational problems that can be solved these computational models.
This course mainly focuses on three major kinds of computational models:
- Finite-state machine
- Pushdown automata
- Turing machine
The students need to design this computational model to solve the problems. The working of each computational model is different.
The concept understanding and computational model design completely based on the involvements of students in teaching and learning process.
Figure 1 shows the Learning pyramid which is created by the Institute of Applied Behavioral Science at National Training Laboratories. The majority of students only retain around 5% of what they learn from their teacher’s lectures, while they retain nearly 90% of what they learn by instructing others [1].
Student knowledge and retention improve when they are exposed to a wide range of educational opportunities. To encourage more student participation, an activity-based approach to teaching and learning was used in the course, and a tutorial was included. Problem based learning, use of some modern tools to demonstrate the working of the computational models, concept maps these techniques are very useful in the teaching and learning process of the Automata Theory Course.
Classroom Challenges while teaching Automata Theory (AT) course:
Due to the complexity of language formalisms, the teaching-learning process for AT is known for its high level of abstraction and is regarded as challenging. It is found that students lack problem-solving skills and believe the subject to be challenging, necessitating greater preparation [2].
Teaching this course in class is very challenging task because students need to design the computational model for given problem statements. There is alternate solution for a given problem. Students need to design the computational models like Finite-state machine (DFA, NFA), Pushdown automata and Turing machine if they know the concept and working principle of these models. Students also need to analyze working of computation model, by providing the input and processing it step by step.
Following are some challenges faced in classroom while teaching to automata theory course:
- Inculcate the concept of working principles of different computational models.
- Difficulty in designing the models for given problem.
- Demonstrating step-wise processing on input by this computational model
- Comparative analysis between working as use of computational model.
- Make them understand use of models in compiler construction phases.
Teaching Methodology adapted for Automata Theory (AT):
By considering above classroom challenge, following student centric approaches are used as teaching -learning methodologies:
- Collaborative Learning
- Problem Based Learning
- Concept Map preparation and presentation
- Use of Visualization based simulation tool like Java Formal Languages and Automata Package (JFLAP)
- Group based tutorial solving.
- Application Based Learning (ABL)
Collaborative Learning
The educational strategy of using groups to improve learning through cooperation is known as collaborative learning. Learners in groups of two or more collaborate to solve issues, finish tasks, or grasp new ideas. In order to boost the confidence among the students that they can able to perform the task allocated slowly by working hand-in-hand.
After teaching any concept in class, problems were assigned to students, faculty helps the students to understand the what is the problem is and what are possible solution to it. Students work together, interact with each other, brainstorm to solve any example.
Problem Based Learning:
In Problem based learning students learn by solving the problems which helps to drive the motivation and learning among them.
As this course is majorly focus on design of different computational modes to solve the different problems, problem base learning is very useful, in which students work on different assignments together to solve problems which includes prediction of regular expression, writing the context free grammar (CFG), design of computational models like finite automata (FA), pushdown automata (PDA), Turing machine) TM) etc.
Concept Map preparation and presentation:
Visual representations of information are called concept maps. Students can learn, remember, and discriminate between concepts with the use of concept maps
Use of visualization Tool:
Use of Visualization tools are very effective tools in the classroom to enhance student interest, comprehension, and retention of information and concepts.
The tool like Java Formal Languages and Automata Package (JFLAP) is available for automata theory to understand the working principal of different computational models.
JFLAP is Java Formal Languages and Automata Package which is an interactive educational software which allows us to design, simulate the state machines and experiment the proof [4].
Group based Tutorial solving
For all mathematical course, tutorial solving play very important role.Tutorial help to develop students’ ability to think and act which helps to gain a deep understanding of the subject. It helps to see the significance and implications of their knowledge so they can apply what they have learned. Group Tutorials are conducted to solve the problems.
Application Based Learning (ABL):
This is an active learning activity which allow students to learn by using their existing knowledge, skills, theories to solve real work problem.
All this active learning techniques are very useful for better learning of Automata Theory course.
Objectives:
The main objective behind to choose this learning methodology
- To inculcate the concept of different computational models.
- To make them understand the working principle of computational models.
- Solve the problem by designing the computational model.
- Demonstrating step-wise processing on input by this computational model.
- Make comparative analysis between working as use of computational model.
- Make them understand the application of the automata theory in compiler design.
Implementation Steps:
A. Collaborative Learning:
Formation of groups as per batches.
Tutorial problems are assigned as per groups.
Students solve the problems in groups during tutorials.
B. Problem Based Learning:
Problem based learning activity taken in class e.g., predict the RE which will represent the RL, design the Computation Models like DFA, NFA, PDA and TM, they also write the CFG for the given language.
Instructor will help them to resolve the understanding of problem statement. Student will prepare the solution and finally, the students present the solution in class.
- Benefits of using collaborative learning and problem-based learning activity:
The students are able to,
- `Work in team.
- Design the computational model to solve the problem.
- Analyze the working of computation model on sample input.
- Present the solution in class which enhance their presentation skills.
- As working in team, built confidence to solve problems.
C. Concept Map:
Activity given for students to design the concepts maps for,
- Deterministic finite automata (DFA), Non- deterministic finite automata (NFA): formal definitions, acceptance and extended functions to illustrate
- Pushdown automata (PDA), Turing machine (TM): formal definitions, working of DA and TM with suitable examples.
Benefits of Concept Map activity:
The students are able to,
- Recall the concept
- Differentiate among the models
- Remembers the things easily.
D. Use of Visualization and simulation tools like JFLAP, Lex and Yacc
JFLAP (Java Formal Languages and Automata Package) is interactive educational software written in Java for experimenting with topics in the computer science area of formal languages and automata theory.
JFLAP allows one to create and simulate computational models.
JFLAP tool
Other some tools suggested and recommend for Automata theory course is Thoth, FLUTE, Deus Ex Machina (DEM, Automata Tutor v3, Automata online tool [7].
Lex Tool:
LEX is a tool used to generate a lexical analyzer. LEX is a program generator designed for lexical processing of character input/output stream. Anything from simple text search program that looks for pattern in its input-output file to a C compiler that transforms a program into optimized code [5].
Yacc Tool:
YACC stands for Yet Another Compiler Compiler. YACC provides a tool to produce a parser for a given grammar. This Tool is used to generate the parser [6].
Both Lex and Yacc Tool was demonstrated in the class, so that students can understand the application of regular expression, context free grammar, parsing in different phases of compiler.
- Benefits of using JFLAP, Lex and Yacc Tools:
The students are able to,
- Use JFALP to design and simulate the model
- Apply the concept learned in real applications (i.e compiler lexical and syntax analysis phase).
- Due to simulation, understand working of models.
Result Analysis:
| Academic Year | Subject Code & Subject Name | Appeared | Passed | Passing% | XX | FF | DD | CD | CC | BC | BB | AB | AA |
| 2021-22 | CI2021-AUTOMATA THEORY | 78 | 71 | 93.42 % | 2 | 5 | 2 | 2 | 10 | 6 | 14 | 18 | 19 |
| 2020-21 | CI202-AUTOMATA THEORY | 73 | 73 | 100% | — | — | — | — | — | 8 | 27 | 27 | 11 |
| 2019-20 | IT2022 AUTOMATA THEORY | 62 | 62 | 100% | — | — | — | — | 3 | 12 | 21 | 18 | 8 |
Above table indicate there is uniform distribution of students in various grade. Also, the count higher grade students get increased.
Attainment of Course AY 2021-22 Sem-II:
| CO | CO Statement | Overall Percentage Attainment |
| CO1 | Predict the Regular Expression for given language | 82.67 |
| CO2 | Design Computational Models for given language | 95.29 |
| CO3 | Construct the Context Free Grammar (CFG) for given language | 100.00 |
| CO4 | Parse the given string using top down & bottom-up parsing | 100.00 |
| CO5 | Prove the properties of regular language and context free language | 100.00 |
Course Exit Survey:
Outcomes of active learning techniques used for this course:
Students are able to,
- Comprehend the concepts of Automata Theory.
- Use modern tools like JFLAP, Lex, Yacc to demonstrate the working principle of different computational models and its use in compiler design.
- Solve the problems like design the different computational model like FA, PDA, TM. Write regular expression to search pattern, write context free grammar for given language.
- Correlate the theoretical concepts to real aspect.
- Remember the concept easily.
- Develop their communication and presentation skill.
- Encourages collaboration and exchange of ideas and perspectives.
- Become an active learner.
- Work in team.
- Make Teaching of Automata very joyful, as this course is hard to teach because of variety of learners.
Conclusion:
Use of collaborative learning, problem solving, concept maps, tutorials and tools like JFLAP, Lex and Yacc really helpful for the better teaching and learning of Automata Theory Course. These activities are really helped for proper engagement of students during class, during tutorials and make the automata concepts more interesting.
References:
[1] https://www.scienceoutside.org/post/pushing-your-teaching-down-the-learning-pyramid
[2] Vijayalaskhmi, M., & Karibasappa, K. G. (2012, July). Activity based teaching learning in formal languages and automata theory-An experience. In 2012 IEEE International Conference on Engineering Education: Innovative Practices and Future Trends (AICERA) (pp. 1-5). IEEE.
[3] https://www.valamis.com/hub/collaborative-learning
[5] https://www.tutorialspoint.com/what-is-lex
[6] https://www.geeksforgeeks.org/introduction-to-yacc/
[7] Ali, L., Sahawneh, N., Kanwal, S., Ahmed, I., & Elmitwally, N. (2023, January). Activity Based Easy Learning Of PushDown Automata. In 2022 International Conference on Cyber Resilience (ICCR). IEEE.