Chat with us on WhatsAppCall Learnizo

KTU 2024 Scheme · Semester 4 · Program Elective I — Artificial Intelligence and Data Science

Introduction to Theory of Computation (PEAIT419) Syllabus

Official KTU 2024 Scheme syllabus for Introduction to Theory of Computation, Semester 4, Program Elective I — Artificial Intelligence and Data Science (Artificial Intelligence and Data Science).

This page compiles APJ Abdul Kalam Technological University's officially published 2024 Scheme syllabus for Artificial Intelligence and Data Science, Semester 4, sourced directly from KTU's official website (ktu.edu.in). Learnizo is an independent online tuition platform and is not affiliated with, endorsed by, or officially connected to APJKTU. The university may revise syllabus content after this page was last updated — always cross-check with the official KTU source for the current, authoritative version.

Course Code

PEAIT419

Credits

4

Teaching Hours

3:0:0:0 (L:T:P:R)

CIE Marks

40

ESE Marks

60

Exam Duration

2 Hrs. 30 Min.

Prerequisites

PCCST205

Semester

Semester 4

Course Objective

To discuss the basic concepts and terminologies related to the theory of computation and to learn and apply the principles of formal languages, grammars, and automata theory. To explore Context-Free Languages and Pushdown Automata To discuss the Chomsky classification of formal languages with a discussion on grammar and automata for regular, context-free, context-sensitive, and unrestricted languages. To discuss the Turing machines' role in defining computability and to explore the limits of computation.

Module-wise Syllabus

Module 1

9 contact hours

Basic concepts: Alphabet, Strings, Languages, Grammar, Automata Deterministic Finite Automata/Accepter (DFA), Language of a DFA, Regular languages, Nondeterministic Finite Automata/Accepter (NFA), NFA with epsilon transitions, Language of an NFA, eliminating epsilon transitions (Proof not expected), Equivalence of NFAs and DFAs (Proof not expected) - The Subset Construction. DFA State Minimization, Applications of finite automata.

Module 2

9 contact hours

Regular expression, Language of a Regular Expression, Equivalence with finite automata (Proof not expected) - Converting FA to Regular Expressions, Converting Regular Expressions to FA, Regular grammar - examples. Closure Properties of Regular Languages (Proof not expected), Pumping Lemma for Regular Languages (Proof not expected), Pumping Lemma as a tool to prove nonregularity of languages. Context Free Language (CFL) and Context-Free Grammar (CFG), Designing CFGs for CFLs, Leftmost and Rightmost Derivations, Parse Trees, Ambiguity in CFGs and CFLs

Module 3

9 contact hours

Simplification of Context-Free Grammars - Eliminating useless symbols and productions, Eliminating epsilon productions, Eliminating unit productions, Chomsky Normal Form (CNF), Converting CFGs into CNF, Greibach Normal Form (definition only). Pushdown Automata (PDA), Language of a PDA, DPDA and NPDA, Designing PDAs for CFLs. Equivalence NPDAs and CFGs (Proof not expected) Pumping Lemma for Context-Free Languages (Proof not expected), Pumping Lemma as a tool to identify Non-Context-Free Languages. Closure Properties of CFLs (Proof not expected), Context Sensitive Grammar and Languages (introduction only)

Module 4

9 contact hours

Turing Machines (TMs) - Turing Machines as language acceptors, Language of a TM, Turing Machines as transducers, Nondeterministic Turing Machines (definition only), Recursive and Recursively Enumerable languages, Unrestricted Grammar (definition only), Chomsky hierarchy, Linear Bounded Automaton as a restricted TM (introduction only). Church-Turing thesis, Encoding of TMs, Universal Turing Machine, Existence of Languages that are not Recursively Enumerable, and Recursive but not Recursively Enumerable, Decidable and Undecidable Problems, The TM Halting Problem.

Course Outcomes

  • CO1Build DFAs and NFAs, summarize the principles of regular languages and grammars, demonstrate the ability to minimize a DFA, and identify the practical applications of FAs.
  • CO2Choose a regular expression for a regular language, identify non- regular languages, and design grammars for context-free languages.
  • CO3Simplify context-free grammars, design pushdown automata, and identify and analyze context-free and non-context-free languages.
  • CO4Construct Turing machines, identify the class of a formal language, apply reduction, and use the halting problem to demonstrate the boundaries of computability.

Assessment Pattern (CIE: 40 marks, ESE: 60 marks)

Continuous Internal Evaluation (CIE)

Attendance5
Assignment / Microproject15
Internal Examination 1 (Written)10
Internal Examination 2 (Written)10

End Semester Examination (ESE)

Total 60 marks, 2 Hrs. 30 Min.. See the official KTU syllabus document for the exact Part A / Part B question pattern for this course.

Textbooks & Reference Books

Textbooks

  • An Introduction to Formal Languages and Automata — Peter Linz and Susan H. Rodger (Jones and Bartlett Publishers, Inc, 7/e, 2022)
  • Introduction to Automata Theory Languages And Computation — John E.Hopcroft, Rajeev Motwani, Jeffrey D.Ullman (Pearson, 3/e, 2015)

Reference Books

  • Introduction to the Theory of Computation — Michael Sipser (Cengage India Private Limited, 3/e, 2014)
  • Introduction to Languages and the Theory of Computation — John C Martin (McGraw-Hill Education, 4/e, 2010)
  • Theory of Computation: A Problem-Solving Approach — Kavi Mahesh (Wiley, 1/e, 2012)
  • Formal Languages and Automata Theory — C K Nagpal (Oxford Higher Education, 1/e, 2011)

Frequently Asked Questions

How many credits is KTU Introduction to Theory of Computation (PEAIT419)?

4 credits, with 3:0:0:0 (L:T:P:R) teaching hours per week, under the KTU 2024 Scheme.

How many modules are in the PEAIT419 syllabus?

4 modules, 36 total contact hours.

What is the CIE and ESE mark split for this course?

CIE (Continuous Internal Evaluation): 40 marks. ESE (End Semester Examination): 60 marks, 2 Hrs. 30 Min.. Total: 100 marks.

What are the recommended textbooks for PEAIT419?

An Introduction to Formal Languages and Automata (Peter Linz and Susan H. Rodger); Introduction to Automata Theory Languages And Computation (John E.Hopcroft, Rajeev Motwani, Jeffrey D.Ullman).

Is this syllabus specific to one branch, or common to others too?

This Semester 4 course is listed under Program Elective I — Artificial Intelligence and Data Science at KTU under the 2024 Scheme — check the course header above for which branches it's common to.

Need help with KTU Introduction to Theory of Computation?

Learnizo offers live, 1-on-1 online tuition for KTU AI&DS subjects — matched to your exact module and semester.