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, ...
Read more

KTU CS332 Network Programming Lab Experiments for S6 CS students

-
Video Classes are available                                       Click Here   for the Playlist List of experiments Experiment No Syllabus PDF 1 Familiarization of Network Configuration Files and Operating System Calls Click 2 Familiarize and understand the use and functioning of System Calls used for Operating system and network programming in Linux Click 3 Processes and Threads Click 4 First Readers Writers Problem Click 5 Second Readers Writers Problem Click 6 Inter process Communication Click    7 Client Server Communication with Socket Programming with TCP Click    8 Client Server Communication with Socket Programming with UDP Click    ...
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