Quick Links

Automata – Introduction

Introduction of Theory of Computation Chomsky Hierarchy Applications of various Automata...

Regular Expression and Finite Automata

Finite Automata Introduction Arden’s Theorem and Challenging Applications | Set 2 L-graphs and what they represent Hypothesis (language regularity) and algorithm (L-graph to NFA) Regular Expressions,Regular Grammar and Regular Languages How to identify if a language is regular or not Arden’s Theorem Finite Automata from Regular Expressions Star Height of Regular Expression and Regular Language Generating regular expression from finite automata Designing Deterministic Finite Automata (Set 1) Designing Deterministic Finite Automata (Set 2) DFA for Strings not ending with “THE” DFA of a string with at least two 0’s and at least two 1’s DFA for accepting the language L = { anbm | n+m=even } DFA machines accepting odd number of 0’s or/and even number of 1’s DFA of a string in which 2nd symbol from RHS is ‘a’ Union process in DFA Concatenation process in DFA DFA in LEX code which accepts even number of zeros and even number of ones. NFA to DFA Conversion Program to Implement NFA with epsilon move to DFA Conversion Minimization of DFA Reversal process in DFA Complementation process in DFA Kleene’s Theorem Part-1 MEALY and MOORE Machines Difference between Mealy machine and Moore machine...

CFG (Context Free Grammar)

Relationship between grammar and language Simplifying Context Free Grammars Closure Properties of Context Free Languages(CFL) Union & Intersection of Regular languages with CFL Converting Context Free Grammar to Chomsky Normal Form Converting Context Free Grammar to Greibach Normal Form Pumping Lemma Check if the language is Context Free or Not Ambiguity in Context Free Grammar Operator grammar and precedence parser Context-sensitive Grammar (CSG) and Language (CSL)...

PDA (Pushdown Automata)

Pushdown Automata Pushdown Automata Acceptance by Final State Construct Pushdown Automata for given languages Construct Pushdown Automata for all length palindrome Detailed Study of PushDown Automata NPDA for accepting the language L = {an bm cn| m,n>=1} NPDA for accepting the language L = {an bn cm | m,n>=1} NPDA for accepting the language L = {anbn | n>=1} NPDA for accepting the language L = {am b(2m) | m>=1} NPDA for accepting the language L = {am bn cp dq| m+n=p+q ; m,n,p,q>=1} Construct Pushdown automata for L = {0n1m2m3n | m,n ? 0} Construct Pushdown automata for L = {0n1m2(n+m) | m,n ? 0} NPDA for accepting the language L = {ambnc(n+m) | m,n ? 1} NPDA for accepting the language L = {amb(n+m)cn| m,n ? 1} NPDA for accepting the language L = {a2mb3m | m ? 1} NPDA for accepting the language L = {amb(2m+1) | m ? 1} NPDA for accepting the language L = {aibjckdl | i==k or j==l,i>=1,j>=1} Construct Pushdown automata for L = {a(2*m)c(4*n)dnbm | m,n ? 0} Construct Pushdown automata for L = {0n1m2(n+m) | m,n ? 0} NPDA for L = {0i1j2k | i==j or j==k ; i , j , k >= 1} NPDA for accepting the language L = {anb(2n) | n>=1} U {anbn | n>=1} NPDA for the language L ={w?{a,b}*| w contains equal no. of a’s and b’s}...

Turing Machine

Turing Machine Turing Machine for addition Turing machine for subtraction | Set 1 Turing machine for multiplication Turing machine for copying data Construct a Turing Machine for language L = {0n1n2n | n?1} Construct a Turing Machine for language L = {wwr | w ? {0, 1}} Construct a Turing Machine for language L = {ww | w ? {0,1}} Construct Turing machine for L = {anbma(n+m) | n,m?1} Construct a Turing machine for L = {aibjck | i*j = k; i, j, k ? 1} Turing machine for 1’s and 2’s complement Recursive and Recursive Enumerable Languages Turing Machine for subtraction | Set 2 Halting Problem Theory of Computation | Applications of various Automata Turing Machine as Comparator...

Decidability

Decidable and undecidable problems Decidability Undecidability and Reducibility NP-Completeness | Set 1 (Introduction) Proof that Hamiltonian Path is NP-Complete Proof that vertex cover is NP complete Computable and non-computable problems...

Quick Links :

Last Minute Notes(LMNs) ‘Quizzes’ on Theory Of Computation ! ‘Practice Problems’ on Theory of Computation !...