Theory of Computation(TOC) / Automata : Complete Pack

Course Curriculum

Chapter 1: Starters : Introduction 🙂

Lecture 1: Introduction of Theory of Computation.

Lecture 2: Formal Languages

Lecture 3: Grammer : Definition

Lecture 4: Classification of Grammars

Lecture 5: Automata : Definition

Lecture 6: Chomsky Hierarchy : Relation among Languages, Grammars and Automata's

Lecture 7: Expressive Power or Recognizing Power of Automata.

Lecture 8: Determinstic and Non-Deterministic Automata.

Lecture 9: Memory States of FA, PDA, TM.

Chapter 2: TOC Fundamentals :

Lecture 1: Alphabets

Lecture 2: String, Length,Empty string(epsilon).

Lecture 3: Substring, Trivial and Non-trivial substring and Note.

Lecture 4: Prefix and Suffix.

Lecture 5: Number of strings with Σ^n.

Lecture 6: Kleene Closure and Positive Closure.

Lecture 7: Language : Definition, Note.

Lecture 8: Empty language, Non-empty language, Finite Language and Infinite Language.

Chapter 3: Regular Languages:

Lecture 1: Introduction

Lecture 2: Types of Finite Automata's

Chapter 4: Deterministic Finite Automata (DFA).

Lecture 1: Deterministic Finite Automata : Definition

Lecture 2: Language of DFA ( L(M)).

Lecture 3: Construct Minimal DFA : Example 1

Lecture 4: Construct Minimal DFA : Example 2

Lecture 5: Construct Minimal DFA : Example 3

Lecture 6: Construct Minimal DFA : Example 4

Lecture 7: Key points : No.of States for starting with, ending with and substring.

Lecture 8: Construct Minimal DFA : Example 5

Lecture 9: Construct Minimal DFA : Example 6

Chapter 5: Construction of Minimal DFA Examples

Lecture 1: Example 7 : L = { 1^2n | n >= 0 }.

Lecture 2: Example 8 : L = { (10)^n | n >= 0 }.

Lecture 3: Example 9 : L = { 1^2n 0^m | m,n >= 1 }.

Lecture 4: Example 10 : L = { 0^2m 1^3n | m,n >= 1 }.

Lecture 5: Example 11 : L = { 0^m 1^n | m,n >= 0 }.

Lecture 6: Example 12 : L = { 0^m 1^n | m >= 1, n >= 0 }.

Lecture 7: Example 13 : L = { 0^m 1^n | m + n = Even }.

Lecture 8: Example 14 : L = { 0^m 1^n | m + n = Odd }.

Chapter 6: Non-Deterministic Pushdown Automata (NFA).

Lecture 1: NFA : Introduction.

Lecture 2: Language of NFA and Note.

Lecture 3: Example 1 : Construction of NFA for language – L = { ε, 10, 01 }

Lecture 4: Example 2 : Construction of NFA for language – L = { 0^n 1 0^m | m,n >= 1 }.

Lecture 5: Example 3 : Construction of NFA for language – L = { 0^2n 1^m | m,n >= 1 }.

Lecture 6: Example 4 : Construction of NFA for language – L = { 0^2m 1^3n | m,n >= 1 }.

Lecture 7: Example 5 : Construction of NFA for language – L = { (01)^2n | n >= 0 }.

Lecture 8: Example 6 : Construction of NFA for language – L = starting with 100.

Lecture 9: Example 7 : Construction of NFA for language – L = ending with 000.

Lecture 10: Example 8 : Construction of NFA for language – L = having substring 101.

Lecture 11: Example 9 : Construction of NFA for language – L =having last two bits are same.

Lecture 12: Example 10 : Construction of NFA for language – L = 4th bit from left end is 1.

Lecture 13: Example 11 : Construction of NFA for language – L = 5th bit from right end is 1.

Lecture 14: Example 12 : Construction of NFA for L = starts and ends with same symbol

Lecture 15: Example 13 : Construction of NFA – L = starts and ends with different symbol.

Chapter 7: NFA to DFA Conversion.

Lecture 1: Algorithm

Lecture 2: Example 1 : Conversion.

Lecture 3: Example 2 : Conversion.

Lecture 4: Example 3 : Conversion.

Lecture 5: Subset Construction.

Lecture 6: Example 4 for constructing DFA.

Lecture 7: Example 5 for constructing DFA.

Chapter 8: Complementation of Regular Language.

Lecture 1: Definition and further with examples.

Lecture 2: Example 1

Lecture 3: Example 2

Lecture 4: Example 3

Lecture 5: Note : on L and L'.

Lecture 6: Example

Chapter 9: Regular Expressions

Lecture 1: Example 1 : L = Set of binary strings starting with 10.

Lecture 2: Example 2 : L = Set of binary strings ends with 10 or 01.

Lecture 3: Example 3 : L = Set of binary strings where 4th symbol from left end is 1.

Lecture 4: Example 4 : L = Set of binary strings of length i) 3 ii) <= 3 iii) >= 3.

Lecture 5: Example 5 : L = Set of binary strings of length i)Even ii)Odd iii) multiple of 3

Lecture 6: Example 6 : L=Number of 0's is i)2 ii)<=2 iii)>=2 iv)Even v)Odd vi)Multiple of 3

Chapter 10: Pushdown Automata (PDA)

Lecture 1: Example 1 : PDA for L = a*

Lecture 2: Example 2 : PDA for L = ab*

Lecture 3: Example 3 : PDA for L = (ab)*a

Lecture 4: Example 4 : PDA for L = { w ∈ (a+b)* | number of a's = Even }

Lecture 5: Example 5 : PDA for L = { w ∈ (a+b)* | |w| = 0 (mod 3) }

Lecture 6: Example 6 : PDA for L = { 0^m 1^n | m=n and m,n >=1 }.

Lecture 7: Example 7 : PDA for L = { 0^m 1^n | m <= n }.

Lecture 8: Example 8 : PDA for L = { 0^m 1^n | m >= n }.

Lecture 9: Example 9 : PDA for L = { 0^m 1^n | m ≠ n and m,n > 0}.

Lecture 10: Example 10 : PDA for L = { 0^m 1^n | m = 2n }.

Lecture 11: Example 11 : PDA for L = { 0^m+n 1^n | m,n >= 1}.

Lecture 12: Example 12 : PDA for L = { 0^m 1^m+n | m,n >= 1 }.

Lecture 13: Example 13 : PDA for L = { 0^m 1^m+n 0^n | m,n >= 1 }.

Lecture 14: Example 14 : PDA for L = { 0^m+n 0^m 1^n | m,n >=1 }.

Lecture 15: Example 15 : PDA for L = { 0^m 1^n 0^m+n | m,n >= 1}.

Lecture 16: Example 16 : PDA for L = { a^m b^n c^p | m = p }.

Lecture 17: Example 17 : PDA for L = { a^m b^n c^p | m = n or n = p }.

Lecture 18: Example 18 : PDA for L = { a^m b^n c^p | n = m + p }.

Lecture 19: Example 19 : PDA for L = { a^m b^n c^n d^m | m,n >= 1 }.

Lecture 20: Example 20 : PDA for L = { w x w^R | w ∈ ( a + b )* }.