1️⃣

Module 1
1️⃣ Introduction to Theory of Computation (ToC)
🧐 What is this course about?
Theory of Computation is one of the most fundamental and abstract courses in Computer Science.
Fundamental and abstract courses → Courses that teach core concepts, theories, and
foundations, not just practical skills.

It doesn't teach you how to write code or build a physical computer. Instead, it teaches you how
computer scientists have defined "computation" over the past 50 years.

Core Question: What kind of problems can a machine solve mechanically?

Key Factors:

Computability: Can it be solved?

Time: How fast can it be solved?

Space: How much memory does it take?

🤖 The Basic Model of Computation

In this subject, we don't look at complex computers like your laptop. We look at abstract
"Machines".
How it works:

1. We design a Machine (System) based on specific Rules.

2. We feed it an Input.

3. The machine processes the input and gives one of two answers:

✅ YES (Accept)
❌ NO (Reject)

💡 Examples of Computability
To understand what machines can and cannot do, let's look at three levels of problems.

Example 1: A Simple Pattern Check (Solvable)

Task: Design a machine that accepts all binary strings that end in 0 (e.g., 110 , 1010 ) and rejects
everything else.

Human Logic: Look at the last digit. Is it 0? Yes →Accept. No →Reject.

Machine Logic: Scan the digits one by one. If the last one scanned is 0, say YES. If it is 1, say
NO.

Module 1 1
 Result: This is possible to design. This uses a Finite State Machine (FSM).

State Transition Diagram for strings ending in 0:

(Here, q0 is the start state, and q1 is the final accepting state)
​ ​

Explanation of Diagram:

Start at q0 : This is the "reject" state (because we haven't seen a 0 at the end yet).
​

Input 1: Stay at q0 (String ends in 1, so reject).

​

Input 0: Move to q1 (String ends in 0, so accept).

​

From q1 : If we get a 1, go back to $q_0$. If we get a 0, stay at $q_1$.

​

Example 2: Syntax Checking (Solvable)

Task: Design a machine that accepts all valid Java code.

Machine Logic: Convert code to binary →Check syntax rules.

Real-life Example: Compilers. If you miss a semicolon, the compiler rejects your code (Syntax
Error). If the code is valid, it compiles.

Result: Possible. This led to the field of Compiler Design.

Example 3: The Infinite Loop Problem (Impossible!)

Task: Design a machine that accepts valid Java code AND ensures it never goes into an
infinite loop.

Result: ❌ NOT POSSIBLE.

Why? You cannot mechanically predict if any given program will run forever or stop. This is a
famous unsolveable problem (known as the Halting Problem).

🏗️ The Layers of Computation (The Hierarchy)

This course is structured in layers, moving from simple machines to powerful ones.

1. Finite State Machine (FSM)

What is it? The simplest model of computation.

Capabilities: Very limited memory. Can only perform low-level calculations (like Example 1
above).

Application: Pattern matching, simple controllers.

Module 1 2
 2. Context-Free Language (CFL)
What is it? More powerful than FSM.

Key Note: Here, "Language" does not mean C++ or Java. In ToC, Language = A Set of Strings.

Capabilities: Can handle nested structures (like checking if brackets (( )) are balanced).

3. Turing Machine (TM)

What is it? Designed by Alan Turing in 1940.

Capabilities: Very powerful. It models how modern computers work. It can perform high-level
computations.

4. Undecidable
What is it? The "Outer Space" of computation.

Meaning: These are problems that cannot be solved mechanically by any machine (like
Example 3, the infinite loop checker).

Here are your comprehensive and simplified study notes for the second lecture. 🎓📘
2️⃣ Prerequisites for Theory of Computation
Before we dive into building machines (like Finite State Machines), we need to learn the "language"
of this subject. Just like you learn ABCs before writing sentences, we need to learn about Symbols,
Alphabets, and Strings first.

1. The Building Blocks 🧱

Here is the hierarchy of how we build things in Theory of Computation:

Symbol →Alphabet →String →Language

A. Symbol
Definition: The most basic unit. It can be anything used to represent information.

Examples:

Letters: a , b , c

Digits: 0 , 1 , 2

Special characters: # , $

B. Alphabet (Σ)
Definition: A finite collection of symbols. We denote it using the Greek letter Sigma (Σ).

Examples:

Σ = {a, b}(An alphabet with two symbols)

Σ = {0, 1}(The binary alphabet)
Σ = {d, e, f , g}

Module 1 3
 C. String
Definition: A sequence of symbols picked from the alphabet.

Examples: (Assuming Σ = {a, b})

a (A string of length 1)

ab (A string of length 2)

aaabb (A string of length 5)

2. What is a Language? 🗣️
Definition: A Language is essentially a Set of Strings.

How it works: You take an alphabet, make some strings, and group them together based on a
rule.

Examples (Let Σ = {0, 1})

Language Name Rule The Set (Strings) Type

L1 Strings of length 2 {00, 01, 10, 11} Finite Set (Ends)

L2 Strings of length 3 {000, 001, 010, 011, … , 111} Finite Set (Ends)
L3 Strings that start with 0 {0, 00, 01, 000, 001, … } Infinite Set (Never ends)

Key Takeaway: A language can be Finite (has a limited number of strings) or Infinite (goes on
forever).

3. Powers of Sigma (Σ) ⚡

We can categorize strings based on their length. This is written as Σraised to a power number.
Let's assume our alphabet is Σ = {0, 1}.
Σ0 (Sigma power 0):
Set of all strings of length 0.

Result: {ϵ}

Note: ϵ(Epsilon) represents an empty string (a string with nothing in it).

Σ1 (Sigma power 1):

Set of all strings of length 1.

Result: {0, 1}

Σ2 (Sigma power 2):

Set of all strings of length 2.

Result: {00, 01, 10, 11}

Σn (Sigma power n):

Set of all strings of length n.

Module 1 4
 4. Cardinality 🔢
Definition: Cardinality simply means the number of elements in a set.

Formula: If our alphabet has 2 symbols (like 0 and 1), the cardinality of Σn is 2n .

Example Check:

Σ2 has length 2. Cardinality = 22 = 4strings.

Σ3 has length 3. Cardinality = 23 = 8strings.

5. Sigma Star (Σ∗ ) 🌟

This is a very special and important term.

Definition: The set of ALL possible strings of ALL possible lengths over an alphabet.

Formula: It is the Union (∪) of all powers of Sigma.

Σ∗ = Σ0 ∪ Σ1 ∪ Σ2 ∪ Σ3 … 
Expanded View:

Σ∗ = {ϵ} ∪ {0, 1} ∪ {00, 01, 10, 11} …

Σ∗ = {ϵ, 0, 1, 00, 01, 10, 11, 000, … }
Important Note: Σ∗ is always an Infinite Set because there is no limit to the length of the
strings.

📝 Summary Hierarchy Flowchart

Explanation of Hierarchy:

1. Symbol: The atomic unit (e.g., 0 ).

2. Alphabet (Σ): The set of allowed symbols (e.g., {0, 1} ).

3. String: A combination of symbols (e.g., 101 ).

4. Language: A set of specific strings (e.g., {101, 110} ).

5. Σ∗ : The set of everything possible you can make with that alphabet.

3️⃣Finite State Machines (FSM)

1. Classification of Finite Automata 🌳

Module 1 5
 Finite Automata (or Finite State Machines) are broadly divided into two categories based on
whether they produce an output or not.

Finite Automata WITH Output:

Mealy Machine: Output depends on the state and the input.

Moore Machine: Output depends only on the state.

Finite Automata WITHOUT Output:

DFA: Deterministic Finite Automata.

NFA: Non-Deterministic Finite Automata.

ϵ-NFA: Epsilon Non-Deterministic Finite Automata.

Note: In this lecture, we focus mainly on DFA.

2. Important Properties of FSM 🧠

Before diving into DFA, remember these two golden rules about Finite State Machines:

1. It is the simplest model of computation.

2. It has very limited memory.

Deterministic Finite Automata (DFA)

1. What is a DFA? 🤖
A DFA (Deterministic Finite Automata) is a machine that reads an input string one symbol at a time
and moves between states. It is called "Deterministic" because for every input, the machine knows
exactly which state to go to next (no guessing!).

2. Structure of a DFA (The Diagram) 🎨

A DFA is usually represented by a State Transition Diagram. Here is how to read one:

Module 1 6
 States (Circles): These represent the conditions or "memory" of the machine. Labeled as
A, B, C, Dor q0 , q1 , etc.
​ ​

Transitions (Edges/Arrows): The lines connecting the circles. They show movement from one
state to another.

Inputs (Labels on Edges): The numbers or letters (like 0 , 1 ) written on the arrows. They tell the
machine when to move.

Example: An arrow from $A$ to $B$ labeled 1 means: "If you are in State A and see input 1,
go to State B."

Start State (Initial State): The state with an arrow coming from nowhere pointing to it. This is
where the machine begins.

Final State (Terminating State): The state with a Double Circle. If the machine stops here after
reading the input, the string is Accepted.

3. The Formal Definition (5 Tuples) 📝

Mathematically, a DFA is defined by a collection of 5 things (called 5-Tuples).

DF A = (Q, Σ, q0 , F , δ) ​

Example from
Symbol Name Explanation
Lecture

Q Set of States The complete list of all circles in the diagram. {A, B, C, D}
Σ Inputs (Alphabet) The symbols the machine can read. {0, 1}
The state where the machine begins (Initial
q0  Start State $A$
State).
​

$F$ Set of Final States The set of accepting states (Double Circles). {D}
Transition The rule book that maps (Current State + Input)
δ See Table Below
Function $\to$ Next State.

Formula for δ :

δ : Q × Σ → Q

Module 1 7
 (Meaning: Take a State from $Q$ and an Input from Σl, and you get a resulting State in $Q$)

4. Example Transition Table 📊

This table replaces the diagram by listing where every state goes for every input.

Start State: A

Final State: D (Double Circle)

Input 0 goes
Current State Input 1 goes to...
to...

A (Start) C B

B D A

C A D

D (Final) B C

4️⃣ DFA Design Example: Strings Starting with 0

1. Problem Statement 🎯
We need to design a Deterministic Finite Automata (DFA) for a specific language L1 . ​

Condition: The language L1 consists of all strings that start with 0.

​

Alphabet (Σ): {0, 1}

2. Analyzing the Language 🧐

Before drawing, let's understand what strings belong to this set and what strings don't.

Valid Strings (Accepted):

0 (Starts with 0)

00 , 01

000 , 010 , 011 ...

Key Observation: As long as the first digit is 0, the rest doesn't matter.

Invalid Strings (Rejected):

1 (Starts with 1)

10 , 11

Module 1 8
 100 ...

Key Observation: If the first digit is 1, the string is immediately invalid.

3. Step-by-Step Construction of the DFA 🛠️

We will build the machine state by state. Let's name our states A, B, and C.

Step 1: The Start State (A)

We begin at State A (Initial State).

We need to decide what happens when we read the first input.

Step 2: Handling Input '0' (The Happy Path)

If the first input is 0:

The condition "starts with 0" is met! 🎉

We move to a new state, State B.

State B must be a Final State (Double Circle) because the string is now valid.

What happens after reaching B?

Since the string already started with 0, any character that comes after (whether 0 or 1)
doesn't change the fact that it started with 0.

So, we create a Self Loop on State B for inputs 0, 1 . It stays accepted forever.

Step 3: Handling Input '1' (The Reject Path)

If the first input is 1:

The condition is violated immediately. 🚫

We move to a new state, State C.

State C is NOT a final state (Single Circle).

What happens after reaching C?

Since the string started with 1, it can never be fixed.

Module 1 9
 We create a Self Loop on State C for inputs 0, 1 . The machine is stuck here.

4. Important Concept: The Dead State 💀

In the step above, State C is called a Dead State (or Trap State).

Definition: A state from which the machine can never reach the Final State.

Why use it? If the input becomes invalid (like starting with 1), we trap the machine in this state
so it can never say "Yes" (Accept).

5. The Final Diagram 🖼️

Here is the logic visualized:

6. Verification (Dry Run) ✅

Let's test our machine with two examples to prove it works.

Example 1: Testing String 001 (Should be Accepted)

Current State Input Read Action New State

A (Start) 0 Correct start. Move to Final. B

B (Final) 0 Loop on B. B

B (Final) 1 Loop on B. B

End Result: Machine ended in State B (Final). ACCEPTED ✅

Example 2: Testing String 101 (Should be Rejected)

Current State Input Read Action New State

Module 1 10
 A (Start) 1 Wrong start! Move to Trap. C

C (Trap) 0 Stuck in Trap. C

C (Trap) 1 Stuck in Trap. C

End Result: Machine ended in State C (Not Final). REJECTED ❌

5️⃣ DFA Design Example: Strings of Length Exactly 2

1. Problem Statement 🎯
We need to design a (DFA) that accepts only strings of length exactly 2.

Alphabet (Σ): {0, 1}

Condition: Length of string must be exactly 2.

2. Analyzing the Language 🧐

Before drawing, let's list out which strings are valid and which are not.

Valid Strings (Accepted):

00 , 01 , 10 , 11

Reason: These are the only strings with exactly two characters.

Invalid Strings (Rejected):

Length 0: ϵ(Empty string)

Length 1: 0 , 1

Length 3+: 000 , 001 , 1110 , etc.

3. Step-by-Step Construction 🛠️
We will build the DFA based on the length of the string processed so far.

Step 1: The Start State (A)

State A: Represents Length 0 (Initial state).

Whether we see 0 or 1 , we have now seen 1 character.

Transition: Move to State B.

Step 2: Reaching Length 1 (State B)

State B: Represents Length 1.

Is this the final length? No. We need exactly 2.

If we read another 0 or 1 , the total length becomes 2.

Transition: Move to State C.

Step 3: Reaching Length 2 (State C - The Goal 🏆)

State C: Represents Length 2.

Module 1 11
 Is this the final length? Yes!

Action: Mark State C as the Final State (Double Circle).

Note: If the string ends here, it is accepted.

Step 4: Handling Length > 2 (State D - The Trap 💀)

What if the string is longer than 2? (e.g., 001 )

From State C, if we read any more inputs ( 0 or 1 ), the length becomes 3. This is invalid.

Transition: Move to State D (Dead State/Trap State).

Loop: Once in State D, stay there forever for any input ( 0 or 1 ).

4. The Final Diagram & Logic 🖼️

Here is the logical flow of the machine:

5. Verification (Dry Run) ✅

Let's test the machine with the examples from the lecture.

Test 1: String 00 (Length 2 - Should

Accept)
1. Start at A.

2. Input 0: Move to B (Length is 1).

3. Input 0: Move to C (Length is 2).

4. End of string. We are at C (Final State).

5. Result: ACCEPTED ✅
Test 2: String 001 (Length 3 - Should
Reject)
1. Start at A.

2. Input 0: Move to B.

3. Input 0: Move to C (Final).

Module 1 12
 4. Input 1: Move to D (Dead State). Test 3: String 1 (Length 1 - Should
5. End of string. We are at D (Not Final).
Reject)

6. Result: REJECTED ❌ 1. Start at A.

2. Input 1: Move to B.

3. End of string. We are at B (Not Final).

a. Result: REJECTED ❌
Here are your study notes for the advanced DFA construction example. 🎓📘
6️⃣ DFA Design: Strings NOT Containing a Substring
1. Problem Statement 🎯
Task: Construct a Deterministic Finite Automata (DFA) that accepts any string over the alphabet
{a, b}that does not contain the sequence "aabb".
Alphabet (Σ): {a, b}

Condition: If the sequence aabb appears anywhere in the string, Reject it. If it never appears,
Accept it.

2. The Strategy: "Divide and Conquer" 🧠

Directly designing a machine for "does not contain" can be very confusing. Instead, we use a
powerful trick called the Complement Method.

The Process:

1. Simplify: First, design a DFA for the opposite problem: Accepts strings that DO contain "aabb".

2. Invert: Once that is done, we simply flip the states (Final ↔Non-Final).

3. Part 1: Designing the "Positive" DFA (Contains aabb )

We need to track the progress of the pattern a → a → b → b .

Module 1 13
 Step-by-Step Construction:
State A (Start):

Goal: We need the first a .

If input is a : Progress! Move to State B (We have a ).

If input is b : No progress. Stay at A.

State B (Has seen a ):

Goal: We need the second a .

If input is a : Progress! Move to State C (We have aa ).

If input is b : Sequence broken ( ab ). We have nothing useful. Go back to A.

State C (Has seen aa ):

Goal: We need the first b .

If input is b : Progress! Move to State D (We have aab ).

If input is a : We have aaa . The last two are still aa , so we are still in the correct position.
Stay at C.

State D (Has seen aab ):

Goal: We need the final b .

If input is b : Success! Pattern found. Move to State E.

If input is a : Sequence broken ( aaba ). The last character is a . This is the start of a new
potential pattern. Go back to State B (Has seen a ).

State E (Final - Has seen aabb ):

Since we are designing the "Contains" machine, once we find aabb , we are happy.

Action: Stay in E forever for any input ( a or b ). This is a Final State.

Module 1 14
 4. Part 2: The "Negative" DFA (Does NOT Contain aabb )
Now, we perform the Complement Operation to solve the original problem.

The Rule:

Make every Final State →Non-Final State.

Make every Non-Final State →Final State.

The Transformation:
State Original Role (Contains aabb) New Role (No aabb)

A Normal Final State (Accept)

B Normal Final State (Accept)

C Normal Final State (Accept)

D Normal Final State (Accept)

E Final (Trap) Non-Final (Dead State)

Why does this work?

In the original machine, we only accepted if we reached the end (found aabb).

In the new machine, we accept everything as long as we don't reach the end. If the input completes
the pattern aabb, it falls into State E, which is now a reject state (Dead State), and the string is
rejected.

5. Final Logic Summary 📝

States A, B, C, D: These are all Accepting States. As long as the string is processing here, it
has not yet formed "aabb".

State E: This is the Reject State (Dead State). If the machine ever reaches here, it means
"aabb" was found, so we must reject the string.

6. Practice Example (Dry Run)

String: aaba (Should be accepted)

1. Start A: Input a →go to B. (Current State B is Final✅)

2. State B: Input a →go to C. (Current State C is Final ✅)
3. State C: Input b →go to D. (Current State D is Final ✅)
4. State D: Input a →go back to B. (Current State B is Final ✅)
5. End: The machine stops at B, which is a Final State. Result: ACCEPTED.

7️⃣ Analyzing a DFA & The Dead State

🧐 The Goal
In previous lectures, we learned how to design a machine. In this lecture, we do the reverse: we are
given a DFA diagram and we must act like detectives to figure out what language it recognizes

Module 1 15
 (i.e., what pattern of strings it accepts).

1. Tracing the DFA Paths 🕵️‍♂️

Let's break down the machine by following the arrows from the Start State (A).

Path 1: The Upper Route (Starting with 1)

Step 1: Start at A. Receive input 1 →Move to State B.

Step 2: At State B:

If we get more 1s, we loop back to B (Stay in B).

Meaning: We can have one 1 or many 1s (e.g., 1 , 11 , 111 ).

Step 3: To finish, we receive input 0 →Move to State D.

Result: State D is a Final State (Double Circle).

Pattern Recognized: Any string that starts with at least one 1 and ends with a 0 .

Examples: 10 , 110 , 1110 .

Path 2: The Lower Route (Starting with 0)

Step 1: Start at A. Receive input 0 →Move to State C.

Step 2: At State C, receive input 1 →Move to State E.

Result: State E is a Final State (Double Circle).

Pattern Recognized: The specific string 01 .

2. Summarizing the Language ($L$) 📝

Combining both paths, we can define the language $L$ that this machine accepts.

Definition in Simple Terms:

The machine accepts strings that are EITHER:

1. The exact string "01".

2. Strings starting with at least one '1' followed by any number of '1's, and ending with a '0'.

Module 1 16
 Formal Definition:

L = {01} ∪ {1n 0 ∣ n ≥ 1}

Note: 1n means "1 repeated n times".

3. The Problem: Missing Transitions 🚫

When we test other strings, we notice some arrows are missing in the diagram.

Example: String 00 .
0
A ​ C
Now at C, if we get another 0, where do we go? Nowhere! The diagram has no arrow for 0

from C.

Strings that "Crash" the Machine:

00 (Stuck at C)

010 (Stuck at E)

1101 (Stuck at D)

In a strict DFA definition, every state must have a transition for every input. If the diagram doesn't
show them, the machine is technically incomplete.

4. The Solution: The Dead State (Trap State) 💀

To make the DFA complete and valid, we add a new state often called the Dead State (or Trap
State).

What is a Dead State?

It is a non-final state (it will never accept the string).

Once the machine enters this state, it can never leave.

It has a self-loop for all inputs ($0, 1$).

How to Fix the Diagram:

We create a new state X (Dead State) and send all "missing" arrows there.

State Missing Input Action

D (Final) 0 or 1 Go to X (Dead State)

C 0 Go to X (Dead State)

E (Final) 0 or 1 Go to X (Dead State)

X (Dead State) 0 or 1 Stay in X

5. Final Visual Structure 🏗️

Here is how the complete machine looks logically:

1. Valid Flows: Go to Final States (D or E).

2. Invalid Flows: If the input violates the pattern (like getting a 0 after 0 ), it goes to State X.

Module 1 17
 3. State X: Loops forever. The string is rejected because X is not a double circle.

8️⃣Regular vs. Non-Regular Languages

1. What is a Regular Language? ✅
A language is considered Regular if and only if a Finite State Machine (FSM) can be designed to
recognize it.

Concept: If you can build a DFA (Deterministic Finite Automata) or NFA (Non-Deterministic
Finite Automata) that accepts the valid strings of a language and rejects the invalid ones, that
language is Regular.

History: In previous lectures, we designed DFAs for specific patterns (like "strings starting with
0"). Those were all Regular Languages.

2. What is a Non-Regular Language? ❌

A language is Non-Regular if it cannot be recognized by any Finite State Machine.

The Root Cause: FSMs fail for these languages because they require Memory.

Why FSMs Fail:

1. Limited Memory: An FSM's "memory" is strictly limited to its current state. It knows "where
I am now," but it cannot remember "what exactly happened 100 steps ago."

2. Cannot Store Strings: An FSM cannot "save" a string to compare it later.

3. Cannot Count: An FSM cannot count indefinitely. It can count small, fixed numbers (like "3
$a$'s"), but it cannot count to an unknown number $n$ (like "$n$ number of $a$'s").

3. Detailed Examples of Non-Regular Languages 🧐

To understand why FSMs fail, let's look at two specific examples where "Memory" or "Counting" is
required.

Module 1 18
 Example 1: The "Copy-Paste" Problem (Pattern Repetition)
Language Structure: w ⋅ w
Meaning: A string followed by the exact same string repeated.

Sample String: ababb ababb

Part 1: ababb

Part 2: Must be exactly ababb again.

Why it is NOT Regular:

To verify this, the machine needs to memorize the entire first part ( ababb ) so it can check if
the second part matches it character by character.

Since an FSM has no storage (like a hard drive or RAM) to save the first string, it cannot
perform this check.

Conclusion: Requires Storing →Non-Regular.

Example 2: The "Equal Count" Problem (Balancing)

Language Structure: L = {an bn }
Meaning: Any number of 'a's followed by the exact same number of 'b's.

Sample Strings:

$n=3$: aaa bbb (3 a's, 3 b's) ✅

$n=4$: aaaa bbbb (4 $a$'s, 4 $b$'s) ✅
$n=3$: aaa bb (3 a's, 2 b's) ❌ (Mismatch)
Why it is NOT Regular:

The machine sees a stream of 'a's. It must count them (e.g., "I have seen 452 $a$'s").

Then, when the '$b$'s start, it must verify that there are exactly 452 'b's.

Since $n$ can be any number (even infinity), the machine would need infinite states to keep
count. An FSM has Finite states.

Conclusion: Requires Counting →Non-Regular.

4. Summary Table 📊
Feature Regular Language Non-Regular Language

Requires more powerful machines (like Pushdown

Recognized By Finite State Machine (FSM)
Automata)

Memory Very Limited (Current State only) Needs Memory (Stack/Tape)

Pattern Matching (e.g., "Starts with

Capabilities Storing Strings, Counting (an bn ), Palindromes
0")

Key Limitation Cannot count to $N$ or store data. N/A

Here are your study notes on Operations on Regular Languages. 🎓📘

Module 1 19
 9️⃣Operations on Regular Languages
In the Theory of Computation, we often manipulate languages (sets of strings) to create new ones.
The three fundamental operations used to build Regular Languages are Union, Concatenation, and
Star.

1. The Three Core Operations 🛠️

A. Union (∪)
Symbol: A ∪ B 

Formal Definition: A ∪ B = {x ∣ x ∈ A or x ∈ B}

Simple Explanation: It works exactly like a set union. You take all the strings from Language A
and all the strings from Language B and put them into one big bucket.

Key Idea: It represents "Either A OR B".

B. Concatenation (∘)
Symbol: A ∘ B (or simply $AB$)

Formal Definition: A ∘ B = {xy ∣ x ∈ A and y ∈ B}

Simple Explanation: You take one string from A and glue it to the beginning of one string from
B. You do this for every possible pair.

Key Idea: It represents "A followed by B".

C. Star Operation (∗) - The Kleene Star

Symbol: A∗ 

Formal Definition: A∗ = {x1 x2 … xk ∣ k ≥ 0 and each xi ∈ A}

​ ​ ​ ​

Simple Explanation: You can pick any number of strings from set A (including zero) and stick
them together in any order.

Important Note: The Star operation always includes ϵ(Epsilon/Empty string) because you can
choose to pick "zero" strings ($k=0$).

Key Idea: It represents "Zero or more repetitions of A".

2. Practical Example 🧮
Let's define two small languages to see how these operations work in practice.

Language A: {pq, r}

Language B: {t, uv}

Step 1: Union ($A \cup B$)

Combine everything.

A ∪ B = {pq, r, t, uv}

Step 2: Concatenation ($A \circ B$)

Module 1 20
 Take every item from A and attach every item from B to its end.

$pq$ combined with t → pqt

$pq$ combined with E

$r$ combined with t → rt

$r$ combined with uv → ruv 
A ∘ B = {pqt, pquv, rt, ruv}

Step 3: Star (A∗ )

Create all possible combinations of strings from A ($pq$ and $r$), including the empty string.

Length 0: ϵ(Always included!)

Length 1: pq, r 

Length 2: pqpq, pqr, rpq, rr 

Length 3: pqpqpq, pqrpq, …

A∗ = {ϵ, pq, r, pqpq, pqr, rpq, rr, … } (Infinite Set)

3. Important Theorems (Closure Properties) 📜

There are two critical rules you must remember about Regular Languages. We say Regular
Languages are "Closed" under these operations.

Theorem 1: Closure under Union

If $A$ and $B$ are Regular Languages, then A ∪ B is also a Regular Language.

Theorem 2: Closure under Concatenation

If $A$ and $B$ are Regular Languages, then A ∘ B is also a Regular Language.

(Note: Regular Languages are also closed under the Star operation, though the lecture specifically
highlighted Union and Concatenation first.)

1️⃣0️⃣Introduction to Non-Deterministic Finite

Automata (NFA)
In this lecture, we move from the predictable world of DFA to the more flexible world of NFA. To
understand NFA, we first need to recall why DFA is called "Deterministic."

1. Recap: Deterministic Finite Automata (DFA) 🤖

The word "Deterministic" means everything is fixed and assured. There is no confusion or
guessing.

Module 1 21
 One Input = One Path: In a DFA, if you are in a specific state and receive a specific input, there
is only one unique next state you can go to.

No Choices: The machine never has to "choose" where to go. It is pre-determined.

No Randomness: The path is strict.

Example: If you are at State A and input is 1, you MUST go to State B. You cannot go
anywhere else.

2. What is NFA (Non-Deterministic Finite Automata)? 🎲

NFA stands for Non-Deterministic Finite Automata. The term "Non-Deterministic" implies that the
future state is not strictly determined by the current state and input alone—there are choices!

Key Characteristics of NFA:

Multiple Next States: For a single input, the machine can move to multiple different states (or
even stay in the same state) at the same time.

Example from Lecture:

State A + Input 0 → Can go to State A OR State C.

State A + Input 1 →Can go to State B OR State D.

Decision Making:

Random Choice: The machine might "guess" which path to take.

Module 1 22
 Parallel Processing: Ideally, you can imagine the machine splitting into multiple copies and
taking ALL valid paths simultaneously.

3. The Epsilon (ϵ) Transition 👻

One of the biggest differences in NFA is the existence of ϵ-moves (Epsilon moves).

What is it? A transition labeled with ϵ(Epsilon).

Meaning: The machine can move from one state to another without reading any input (on an
empty string).

Rule: This feature is exclusive to NFA. You will NEVER see an ϵ-transition in a standard DFA.

4. Comparison: DFA vs. NFA ⚔️

Feature DFA (Deterministic) NFA (Non-Deterministic)

Exactly one unique state for every Can have zero, one, or multiple next states for an
Next State
input. input.

Ambiguity No ambiguity. Allowed (Choices exist).

ϵMoves Not Allowed. Allowed (Can move without input).

Backtracking Not needed. Allowed/Implicit (via parallel paths).

Easy to build directly in Easier to design conceptually, but harder to implement

Implementation
hardware/code. directly.

1️⃣1️⃣Formal Definition of NFA

In this lecture, we formalize what an NFA is mathematically. We also explore why it is different from
a DFA using a specific example.

1. Example: NFA for Strings Ending in '0' 🎯

The lecture uses a specific NFA to explain the concepts.

Goal of the Machine: Accept all strings that end with 0.

Structure:

State A (Start State):

Input 0: Can go to A OR go to B. (Multiple

choices!)

Input 1: Stays in A.

State B (Final State):

Input 0 or 1: No transition defined. (Dead

end).

Why is this easier than DFA?

In a DFA, we must strictly define exactly one path for every input. In an NFA, we can just say "If it's
a 0, maybe go to the end?" and leave other parts undefined. This makes designing NFAs much

Module 1 23
 simpler and more flexible.

2. Key Observations: NFA vs. DFA 🔍

Before the math, notice these two major practical differences:

1. Multiple Next States:

In the example, from State A, input 0 leads to {A, B}.

DFA: One input →One State.

NFA: One input →Many States (or zero).

2. Incomplete Transitions:

In the example, State B has no arrows for 0 or 1 .

DFA: Illegal. Every state must respond to every input.

NFA: Perfectly legal. If a path stops, that branch just dies.

3. The Formal Definition (5 Tuples) 📝

Just like a DFA, an NFA is defined by 5 components (tuples).
NF A = (Q, Σ, q0 , F , δ)
​

Symbol Name Definition Value in Example

Q States The finite set of all states. {A, B}

Σ Alphabet The set of allowed inputs. {0, 1}
q0  ​
Start State The initial state where we begin. A
F Final States The set of accepting states. {B}
δ Transition Function The rule mapping inputs to next states. See Section 4

4. The Transition Function (δ ) - The Big Difference ⚡

This is the most important part of the lecture.

DFA Formula: δ : Q × Σ → Q
(One state + One input →One Result)

NFA Formula: δ : Q × Σ → 2Q 
(One state + One input →A Set of Possible Results)

Why 2Q ? (The Power Set Explanation)

2Q represents the Power Set of Q, which means "all possible subsets of states."
Let's look at the possibilities for a machine with 2 States (A, B):

1. Go to {A}

2. Go to {B}

3. Go to {A, B} (Both at once)

Module 1 24
 4. Go to ∅(Nowhere/Dead State)

Total possibilities = 4.
Mathematical formula: 2number of states = 22 = 4.
If we had 3 States (A, B, C):
Possibilities: {A}, {B}, {C}, {A, B}, {B, C}, {A, C}, {A, B, C}, ∅.

Total = 23 = 8.
Conclusion:
Since an NFA allows us to go to any combination of states (or none), the transition function maps to
the Power Set (2Q ).

1️⃣2️⃣How NFA Processes Strings (Solved Examples)

In a Deterministic Finite Automata (DFA), the machine is always in exactly one state at a time.
However, in an NFA (Non-Deterministic Finite Automata), the machine can exist in multiple states
simultaneously because of branching transitions.
We will analyze the NFA from the previous lecture:

Goal: Accept strings ending with 0 .

States: Start State A, Final State B.

Transitions:
0
A ​ {A, B}(Split)
1
A ​ {A}
B : has no transitions (Dead end).

✅ Solved Example 1: Accepted String

Input String: 100

(Since this ends in 0, it should be accepted.)

Step-by-Step Execution:

1. Start: We begin at State A.

Module 1 25
 2. Input '1':

From A, input 1 goes to A.

Current States: { A }

3. Input '0':

From A, input 0 goes to A AND B.

Current States: { A, B } (The machine is now in both states at once).

4. Input '0':

We must check transitions for all current states ({A, B}):

From A: Input 0 goes to { A, B }.

From B: Input 0 goes nowhere (ϕor Dead).

Final States: { A, B }

Conclusion:
At the end of the string, the active states are {A, B}.

Is A a Final State? No.

Is B a Final State? YES.

Result: Since at least one active state is Final, the string is ACCEPTED.

❌ Solved Example 2: Rejected String

Input String: 01
(Since this ends in 1, it should be rejected.)

Step-by-Step Execution:

1. Start: We begin at State A.

2. Input '0':

From A, input 0 goes to A AND B.

Current States: { A, B }

3. Input '1':

We check transitions for all current states:

From A: Input 1 goes to A.

From B: Input 1 goes nowhere ($\phi$).

Module 1 26
 Final States: { A }

Conclusion:
At the end of the string, the only active state is {A}.

Is A a Final State? No.

Result: None of the active states are Final. The string is REJECTED.

📜 Core Concept: When does an NFA Accept?

This is the most important definition to remember for exams.

Formal Rule:

🌟An NFA accepts a string if, after reading the entire input, the set of active states contains at
least one Final State.

Logic:

The machine tries all possible paths simultaneously.

If any one of those paths succeeds (reaches a Final State), the whole string is considered
valid.

We don't care if other paths reached a dead end (ϕ) or a non-final state.

Summary Formula:
Let S be the set of states the machine is in after reading the string.

If S ∩F =
 ∅(Intersection with Final States is not empty) →ACCEPT
Otherwise →REJECT

1️⃣3️⃣Designing NFA: Examples & Concepts

In this lecture, we explore how to design NFAs for specific languages. We will see that designing an
NFA is often much simpler and "cleaner" than designing a DFA because we don't need to worry
about invalid paths—we can just let them "die."

Example 1: Strings Starting with '0' 🏁

Task: Design an NFA that accepts all strings that start with 0.

Module 1 27
 1. Analyzing the Logic
Valid Strings: 0 , 00 , 01 , 000 ... (Must start with 0).

Invalid Strings: 1 , 10 , 11 ... (Starts with 1).

2. Construction Steps
1. Start State (A):

If input is 0 : Move to State B. This satisfies our condition.

2. State B (Final State):

Since the string has already started with 0 , we are happy.

We can accept anything that comes after.

Action: Loop on B for inputs 0, 1 .

3. Handling the Invalid Case (Starting with '1')

In DFA: We would need to create a specific Dead State (Trap State). If the string starts with 1 ,
we send it there to loop forever and be rejected.

In NFA: We simply do nothing. We do not define a transition for input 1 at State A.

4. Important Concept: Dead Configuration 💀

When an NFA is in a state and receives an input for which there is no outgoing arrow, the machine
halts and the branch dies.

Definition: This situation is called a Dead Configuration.

Result: The string is rejected (unless another parallel branch succeeds).

Comparison:

DFA: Uses Dead State (Explicit trap).

NFA: Uses Dead Configuration (Implicit rejection by crashing).

Example 2: Strings of Length Exactly 2 📏

Task: Design an NFA that accepts strings of length exactly 2.

Language: {00, 01, 10, 11}

1. Construction Steps
1. Start State (A): Represents Length 0.

Module 1 28
 Input 0 or 1 : Move to State B.

2. State B: Represents Length 1.

Input 0 or 1 : Move to State C.

3. State C (Final State): Represents Length 2.

Mark as Final.

2. Handling "Too Long" Strings

What happens if the string is 001 (Length 3)?

The machine reaches State C (Final) after 00 .

Then it reads 1 .

Action: There is no outgoing arrow from C.

Result: The machine enters a Dead Configuration and rejects the string.

Advantage: In a DFA, we would have needed an extra "Trap State" for length 3+. In NFA, we just
stop drawing! ✨
📝 Summary: DFA vs. NFA Design
Feature DFA Design NFA Design

Mandatory. Every state must have an arrow for Optional. You only draw the arrows
Completeness
every input (0 and 1). you need.

Ignore them. They lead to a Dead

Invalid Inputs Must send them to an explicit Dead/Trap State.
Configuration.

Complexity More complex, more states needed. Simpler, cleaner, fewer states.

1️⃣4️⃣NFA Design Practice: 5 Core Examples

In this lecture, we focus on quickly designing Non-Deterministic Finite Automata (NFA) for specific
string patterns. We will see how the flexibility of NFAs (guessing and parallel paths) makes this
much easier than designing DFAs.

🌟[Link]
watch the trick, and after making the NFA with this trick check it on few diverse examples.

1. Language L1 : Strings that End with '1'

​ 🏁
Goal: Accept any string where the last digit is 1 .

Module 1 29
 Logic:

Start State (A): We don't care what happens at the beginning. We can have any number of
0 s or 1 s. So, we loop 0, 1 on the start state.

The Magic Guess: When we see a 1 , the machine has two choices:

1. Stay in A (Thinking: "This is not the last 1").

2. Move to B (Thinking: "This IS the last 1").

Final State (B): Once we reach B, we stop. If the string ends there, it's accepted.

Why NFA is cool here: In a DFA, we would need to handle what happens if a 0 comes after the 1
(go back to start). In an NFA, if a 0 comes after we moved to B, that path just "dies" (Dead
Configuration), and the machine relies on the path that stayed in A.

2. Language L2 : Strings that Contain '0'

​ 🔍
Goal: Accept any string that has at least one 0 anywhere.

Logic:

Start State (A): The 0 can appear later, so we loop 0, 1 initially to skip any prefix.

The Trigger: When we see the specific symbol 0 , we can choose to move to State B.

Final State (B): Once we have found our 0 , the condition is met! We don't care what comes
after. So, we loop 0, 1 on the final state forever.

3. Language L3 : Strings that Start with '10'

​ 🚦

Module 1 30
 Goal: The string must begin with 1 followed by 0 .

Logic:

Step 1: From Start (A), strict transition on 1 to State B.

Step 2: From State B, strict transition on 0 to State C.

Final State (C): Once we reach C, the condition ("Starts with 10") is satisfied. We don't care
about the rest of the string, so we loop 0, 1 on C forever.

Note: If the string starts with 0 or 11 , the path dies immediately.

4. Language L4 : Strings that Contain the Substring '01'

​ 🔗
Goal: Accept any string that has 01 together in that order.

Logic:

Start State (A): The pattern 01 can be anywhere. Loop 0, 1 to wait for it.

Detection:

See 0 ? Move to State B.

From B, see 1 ? Move to State C.

Final State (C): We found 01 . Condition met. Loop 0, 1 forever on C.

5. Language L5  : Strings that End with '11'

​ 🔚
Goal: Accept any string where the last two digits are 11 .

Logic:

Start State (A): Loop 0, 1 to handle the beginning of the string.

The Transition:

See 1 ? Guess it's the start of the ending sequence. Move to B.

From B, see another 1 ? Move to C (Final).

Final State (C): DO NOT put a loop here.

Module 1 31
 Why? Because if we get more input after reaching C, then 11 was not the end.

By leaving C with no transitions, any extra input causes the branch to die (Dead
Configuration), ensuring we only accept if the string truly ends at 11 .

📝 Homework Assignment
The lecturer posed a challenge for you:

1. Task: Convert the 5 NFAs above into their equivalent DFAs.

2. Question: What is the minimum number of states required for each DFA?

Hint: Try to trace the states logically. For example, "Ends with 11" usually requires 3 states in
NFA but might need the same or more in DFA to track overlaps (like 111 ).

Module 1 32