TAFL Unit 1 Handwritten Notes AKTU (BCS402)

AKTU · BTECH · Semester 4 · Theory of Automata and Formal Languages · Unit 1 · Handwritten Notes

AKTU Theory of Automata and Formal Languages (BCS402) Unit 1 handwritten notes for B.Tech Semester 4 – Basic Concepts and Automata Theory. Topics…

Open the interactive reader to study this resource on AcademicArk.

Unit 1: Basic Concepts and Automata Theory – AKTU syllabus topics

Introduction to Theory of Computation: Alphabet Symbol String Formal Languages, Automata Computability Complexity Overview
Deterministic Finite Automaton: DFA Definition and Representation, String and Language Acceptability
Non Deterministic Finite Automaton: Equivalence of DFA and NFA, NFA with Epsilon Transition, Equivalence NFA With Without Epsilon
Finite Automata with Output: Moore Machine, Mealy Machine, Equivalence of Moore and Mealy
Minimization of Finite Automata

Q3b. Express in the minimum state automata equivalent to DFA described in below figure: (7 marks, 2024-25)
Q3b. Construct a minimum state automata equivalent to a DFA whose transition table is as follows where q3 and q4 are final state. (transition table with states Q0-Q7 over inputs a,b given) (10 marks, 2022-23)
Q3a. Construct a DFA corresponding to the following NFA: (7 marks, 2024-25)
Q2a. Construct a Finite automata (DFA) which accepts all binary numbers whose decimal equivalent is divisible by 4 over Σ = {0, 1}. (7 marks, 2023-24)
Q1a. Define the term "Alphabet" in the context of automata theory. (2 marks, 2024-25)
Q1b. Differentiate between DFA and NFA. (2 marks, 2024-25)
Q2a. Construct a DFA for ternary number divisible by 4. (10 marks, 2022-23)
Q3a. Construct a DFA equivalent to the NFA (10 marks, 2022-23)
Q4b. Explain in detail about the Myhill-Nerode theorem using suitable example. (10 marks, 2021-22)
Q6b. Minimize the given DFA shown below (Figure A). (10 marks, 2021-22)