Theory of Automata and Formal Languages (BCS402) important questions and topics for AKTU
These are ranked by how often AKTU repeats them across 6 papers. Repeated questions and "very likely" topics are the safest marks in the exam.
Most repeated Theory of Automata and Formal Languages questions
- Express in the minimum state automata equivalent to DFA described in below figure: (7 marks, 2025, Minimization of Finite Automata) – also asked in 2018, 2019, 2022, 2023, 2024
- Using Pumping Lemma, show that the language L = {aⁿbⁿcⁿ | n ≥ 0} is not regular. (7 marks, 2025, Pumping Lemma for Regular Languages) – also asked in 2018, 2019, 2022, 2023, 2024
- Discuss Post's Correspondence Problem (PCP) with an example showing undecidability. (7 marks, 2025, Recursive and RE Languages) – also asked in 2018, 2019, 2022, 2023, 2024
- Prove using Arden's Theorem the regular expression for the following transition diagram: States: A (start), B (final). Transitions: A --a--> A, A --b--> B, B --a--> B (7 marks, 2025, Arden's Theorem) – also asked in 2018, 2019, 2023, 2024
- Design a PDA that accepts the language L = {ww^R | w ∈ {a, b}*}. (7 marks, 2025, Nondeterministic Pushdown Automata) – also asked in 2018, 2019, 2022, 2023
High-probability Theory of Automata and Formal Languages topics
- Context Free Grammar (Unit 3: Regular and Non-Regular Grammars) – asked 17 times in 2018, 2019, 2022, 2023, 2024, 2025
- Non Deterministic Finite Automaton (Unit 1: Basic Concepts and Automata Theory) – asked 10 times in 2018, 2019, 2022, 2023, 2024, 2025
- Minimization of Finite Automata (Unit 1: Basic Concepts and Automata Theory) – asked 8 times in 2018, 2019, 2022, 2023, 2024, 2025