KTU CS301 Theory of Computation Notes

-

 


Quick Revision notes on KTU CS301 Theory of Computation (TOC) are available....




Module


Syllabus
Quick Revision Notes
Module 1 Introduction to Automata Theory and its significance. Type 3 Formalism: Finite state automata – Properties of transition functions, Designing finite automata, NFA, Finite Automata with Epsilon Transitions, Equivalence of NFA and DFA, Conversion of NFA to DFA, Equivalence and Conversion of NFA with and without Epsilon Transitions. Click Here
Module 2 Myhill-Nerode Theorem, Minimal State FA Computation. Finite State Machines with Output- Mealy and Moore machine (Design Only), Two- Way Finite Automata. Regular Grammar, Regular Expressions, Equivalence of regular expressions and NFA with epsilon transitions. Converting Regular Expressions to NFA with epsilon transitions Equivalence of DFA and regular expressions, converting DFA to Regular Expressions. Click Here
Module 3 Pumping Lemma for Regular Languages, Applications of Pumping Lemma. Closure Properties of Regular sets (Proofs not required), Decision Problems related with Type 3 Formalism Type 2 Formalism:- Context-Free Languages (CFL), Context-Free Grammar (CFG), Derivation trees, Ambiguity, Simplification of CFG, Chomsky Normal Form, Greibach normal forms Click Here
Module 4 Non-Deterministic Pushdown Automata (NPDA), design. Equivalence of acceptance by final state and empty stack in PDA. Equivalence between NPDA and CFG, Deterministic Push Down Automata, Closure properties of CFLs (Proof not required), Decision Problems related with Type 2 Formalism Click Here
Module 5 Pumping Lemma for CFLs, Applications of Pumping Lemma. Type 1 Formalism: Context-sensitive Grammar. Linear Bounded Automata (Design not required) Type 0 Formalism: Turing Machine (TM) – Basics and formal definition, TMs as language acceptors, TMs as Transducers, Designing Turing Machines. Click Here
Module 6 Variants of TMs -Universal Turing Machine, Multi- tape TMs, Non Deterministic TMs, Enumeration Machine (Equivalence not required), Recursively Enumerable Languages, Recursive languages, Properties of Recursively Enumerable Languages and Recursive Languages, Decidability and Halting Problem. Chomsky Hierarchy Click Here

Comments

Post a Comment

Popular posts from this blog

KTU CS304 Compiler Design S6 CS/IT

-
Video Classes are available                                       Click Here   for the Playlist All Previous University Question Papers Notes Module Syllabus Notes 1 Introduction to compilers – Analysis of the source program, Phases of a compiler, Grouping of phases, compiler writing tools – bootstrapping Lexical Analysis: The role of Lexical Analyzer, Input Buffering, Specification of Tokens using Regular Expressions, Review of Finite Automata, Recognition of Tokens. Click 2 Syntax Analysis: Review of Context-Free Grammars – Derivation trees and Parse Trees, Ambiguity. Top-Down Parsing: Recursive Descent parsing, Predictive parsing, LL(1) Grammars. Click 3 Bottom-Up Parsing: Shift Reduce parsing – Operator precedence parsing (Concepts only) LR parsing – Constructing SLR parsing tables, Constructing, Canonical LR parsing tables and Constructing LALR parsing tables. Click 4
Read more

CS428 Blockchain Technologies - S8 CSE - Elective

-
Syllabus Textbook Module Syllabus PPT 1 Introduction to Cryptography, Symmetric cryptography – AES. Asymmetric cryptography – RSA. Elliptic curve cryptography, Digital signatures – RSA digital signature algorithms. Secure Hash Algorithms – SHA-256. Applications of cryptographic hash functions – Merkle trees, Distributed hash tables. Click 2 Blockchain – Definition, architecture, elements of blockchain, benefits and limitations, types of blockchain. Consensus – definition, types, consensus in blockchain. Decentralization – Decentralization using blockchain, Methods of decentralization, Routes to decentralization, Blockchain and full ecosystem decentralization. Click 3 Consensus Algorithms, Crash fault-tolerance (CFT) algorithms – Paxos, Raft. Byzantine fault- tolerance (BFT) algorithms – Practical Byzantine Fault Tolerance (PBFT), Proof of work (PoW), Proof of stake (PoS), Types of PoS. Bitcoin –
Read more

KTU CST362 Programming in Python S6 CSE Elective

-
  Text Book 1 - Downey Text Book 2 - Lambert Solution for Programming Questions from Model Question Paper Question Bank Model Questions from all Modules Notes/PP Module Syllabus PPT 1 Getting started with Python programming – Interactive shell, IDLE, iPython Notebooks,Detecting and correcting syntax errors, How Python works. The software development process – A case study. Basic coding skills – strings, assignment, and comments, Numeric data types and character sets, Expressions, Using inbuilt functions and modules. Control statements – Iteration with for/while loop, Formatting text for output, A case study, Selection structure (if-else, switchcase), Conditional iteration with while, A case study, Testing control statements, Lazy evaluation. Click 2 Strings and text files – Accessing characters, substrings, Data encryption, Strings and number system, String methods, Text files, A case study on text analysis. Design with Fu
Read more