day two of theory of computation

 1. The Formal Definition (The 5-Tuple) 

A DFA is mathematically defined as a 5-tuple

$M=(Q,\Sigma ,\delta ,q_0,F)$

: 

• 

  $Q$
  : A finite set of states (e.g.,
  

  $\{q_0,q_1,q_2\}$
  ).
• 

  $\Sigma$
  : A finite set of symbols called the alphabet (e.g.,
  

  $\{0,1\}$
  ).
• 

  $\delta$
  : The transition function, defined as
  

  $\delta :Q\times \Sigma \to Q$
  . This ensures that for every state and input, there is exactly one destination state.
• 

  $q_0$
  : The start state (
  

  $q_0\in Q$
  ).
• 

  $F$
  : The set of accept states or final states (
  

  $F\subseteq Q$
  ). 

2. Key Rules of DFA Design 

• Determinism: Every state must have exactly one outgoing arrow for every symbol in the alphabet.
• No Epsilon (
  

  $ϵ$
  ) Moves: A DFA cannot change states without consuming an input symbol.
• Completeness: If a state should not lead to an acceptance path, it must transition to a "Dead State" (trap state) where it stays for all subsequent inputs. 

3. Practical Design Examples 

Common Day Two exercises include building machines for specific languages: 

• Strings ending with '01': Requires at least 3 states to track the last two seen characters.
• Even number of 'a's: Uses two states to flip-flop between "Even" (Accepting) and "Odd" (Non-Accepting) counts.
• Strings starting with 'ab': Uses a "Dead State" for any string that begins with 'b' or 'aa'. 

day one of theory of computation

 1. The Three Pillars of ToC 

• Automata Theory: Studying abstract mathematical models (machines) to understand how they process input.
• Computability Theory: Identifying which problems are "solvable" by a computer and which are "undecidable" (e.g., the Halting Problem).
• Complexity Theory: Measuring how efficiently a problem can be solved in terms of time (steps) and space (memory). 

2. Basic Definitions (The Vocabulary) 

To begin, you must master these fundamental building blocks: 

• Symbol: The smallest unit of data (e.g., 0, 1, a, b).
• Alphabet (
  

  $\Sigma$
  ): A finite, non-empty set of symbols (e.g., binary
  

  $\Sigma =\{0,1\}$
  ).
• String: A finite sequence of symbols from an alphabet (e.g., 0101).
• Language: A set of strings (e.g., the set of all binary strings that end in 1). 

3. Introduction to Finite Automata (FA) 

The first model usually introduced is the Finite State Machine, which has no external memory. 

• Deterministic Finite Automata (DFA): For every state and input symbol, there is exactly one transition to a next state.
• Non-Deterministic Finite Automata (NFA): Can have multiple possible next states for the same input, providing a more flexible but equivalent model for regular languages. 

📘 PAPER 6 – DATA COMMUNICATION & NETWORKS ( UNIT 5 – APPLICATION LAYER & NETWORK APPLICATIONS )

 

🔴 UNIT 5 – APPLICATION LAYER & NETWORK APPLICATIONS

---

🟦 1. Application Layer – Introduction

✅ Definition

The Application Layer is the topmost layer of the OSI model.
It provides services directly to the user.

👉 It acts as an interface between:

• User

• Network

---

🟦 2. Functions of Application Layer

✔ File transfer
✔ Email communication
✔ Remote login
✔ Web browsing
✔ Network management

---

🟦 3. Application Layer Protocols

---

🔹 1. FTP (File Transfer Protocol)

Purpose:

Used to transfer files between client and server.

Features:

✔ Reliable
✔ Uses TCP
✔ Supports upload & download

Ports:

• Port 21 → Control

• Port 20 → Data

---

🔹 2. TFTP (Trivial File Transfer Protocol)

Features:

✔ Simpler than FTP
✔ Uses UDP
✔ No authentication
❌ Less secure

---

🔹 3. SMTP (Simple Mail Transfer Protocol)

Purpose:

Used to send emails

Characteristics:

✔ Push protocol
✔ Works on TCP
✔ Port 25

---

🔹 4. POP3 (Post Office Protocol)

Purpose:

Used to receive emails

Features:

✔ Downloads mail
✔ Deletes mail from server

---

🔹 5. IMAP (Internet Message Access Protocol)

Difference from POP:

✔ Emails remain on server
✔ Can access from multiple devices

---

🔹 6. HTTP (Hyper Text Transfer Protocol)

Used for:

✔ Web browsing
✔ Communication between browser and server

Features:

✔ Stateless
✔ Uses TCP
✔ Port 80

---

🔹 7. HTTPS

Secure version of HTTP

Uses:
✔ SSL / TLS encryption
✔ Port 443

---

🟦 4. DNS (Domain Name System)

Definition:

DNS converts:

Domain Name → IP Address

Example:

www.google.com → 142.250.192.14

---

DNS Hierarchy:

1. Root Server

2. TLD Server

3. Authoritative Server

---

🟦 5. SNMP (Simple Network Management Protocol)

Purpose:

Used to manage and monitor network devices.

Components:

✔ Manager
✔ Agent
✔ MIB

---

🟦 6. TELNET

Definition:

Allows remote login to another computer.

❌ Not secure
✔ Replaced by SSH

---

🟦 7. Network Applications

Common Applications:

✔ Email
✔ File sharing
✔ Video conferencing
✔ Web browsing
✔ Cloud services

---

🟦 8. Client–Server Model

Client:

Requests services

Server:

Provides services

Example:
Browser → Web Server

---

🟦 9. Peer-to-Peer Network

Features:

✔ No central server
✔ Each node is client & server
✔ Used in file sharing

---

🟦 10. Internet & Public Networks

Internet:

Global network of networks

Public Network:

Accessible by all users

---

📌 EXAM IMPORTANT QUESTIONS (UNIT 5)

✔ Explain FTP, SMTP, POP, IMAP
✔ Difference between HTTP & HTTPS
✔ DNS working
✔ Application layer protocols
✔ Client-server vs P2P
✔ SNMP explanation

📘 PAPER 6 – DATA COMMUNICATION & NETWORKS (UNIT 4 – TRANSPORT, SESSION & PRESENTATION LAYERS)

 

🔴 UNIT 4 – TRANSPORT, SESSION & PRESENTATION LAYERS

---

🟦 PART A: TRANSPORT LAYER

---

1️⃣ Transport Layer – Introduction

✅ Definition

The Transport Layer is responsible for:
✔ End-to-end communication
✔ Reliable data transfer
✔ Flow control
✔ Error control

It works between:
➡ Application Layer and Network Layer

---

2️⃣ Functions of Transport Layer

✔ Segmentation & Reassembly
✔ Service point addressing (Port numbers)
✔ Flow control
✔ Error control
✔ Connection control

---

3️⃣ Transport Layer Protocols

🔹 1. TCP (Transmission Control Protocol)

Features:

✔ Connection-oriented
✔ Reliable
✔ Error-free transmission
✔ Flow control
✔ Congestion control

---

TCP Services:

• Sequencing

• Acknowledgment

• Retransmission

• Full-duplex communication

---

TCP Header Contains:

• Source port

• Destination port

• Sequence number

• Acknowledgment number

• Flags

• Window size

---

4️⃣ TCP Connection Management

🔹 Three-Way Handshake

1️⃣ SYN →
2️⃣ SYN + ACK →
3️⃣ ACK →

✔ Connection established

---

🔹 Connection Termination

Uses:

• FIN

• ACK

---

5️⃣ UDP (User Datagram Protocol)

Features:

✔ Connectionless
✔ Fast
✔ No error checking
✔ No flow control

---

Used In:

• Video streaming

• Online games

• Voice calls

---

6️⃣ TCP vs UDP

TCP	UDP
Reliable	Unreliable
Connection-oriented	Connectionless
Slower	Faster
Error control	No error control
Used for emails	Used for video

---

🟦 PART B: SESSION LAYER

---

7️⃣ Session Layer – Introduction

Definition:

Session layer manages:
✔ Session establishment
✔ Session maintenance
✔ Session termination

---

Functions:

• Dialog control

• Synchronization

• Session checkpointing

---

Example:

✔ Video conferencing
✔ Online login sessions

---

🟦 PART C: PRESENTATION LAYER

---

8️⃣ Presentation Layer – Introduction

Definition:

Presentation layer is responsible for:
✔ Data formatting
✔ Encryption
✔ Compression

---

Functions:

---

🔹 1. Data Translation

Converts data format (ASCII, EBCDIC)

---

🔹 2. Encryption

Provides security

---

🔹 3. Compression

Reduces data size

---

9️⃣ Encryption Techniques

🔹 Symmetric Encryption

• Same key for encryption & decryption

• Example: AES

---

🔹 Asymmetric Encryption

• Public key + Private key

• Example: RSA

---

🔟 Comparison of Layers

Layer	Main Function
Transport	End-to-end delivery
Session	Session control
Presentation	Data formatting & security

---

📌 EXAM IMPORTANT QUESTIONS (UNIT 4)

✔ Explain TCP/IP
✔ TCP vs UDP
✔ Three-way handshake
✔ Functions of session layer
✔ Functions of presentation layer
✔ Encryption techniques

📘 PAPER 6 – DATA COMMUNICATION & NETWORKS (UNIT 3 – NETWORK LAYER) university of allahabad

 

🔴 UNIT 3 – NETWORK LAYER

---

1️⃣ Network Layer – Introduction

✅ Definition

The Network Layer is responsible for:

• Routing packets

• Logical addressing

• Path selection

• Congestion control

👉 It ensures data reaches the correct destination network.

---

2️⃣ Functions of Network Layer

✔ Logical addressing
✔ Routing
✔ Packet forwarding
✔ Congestion control
✔ Internetworking

---

3️⃣ Network Layer Services

🔹 Connection-Oriented Service

• Establishes connection before transmission

• Reliable

• Example: Virtual circuits

---

🔹 Connectionless Service

• No prior connection

• Fast but unreliable

• Example: Internet (IP)

---

4️⃣ Routing

✅ Definition

Routing is the process of selecting the best path to transfer data from source to destination.

---

5️⃣ Types of Routing

---

🔹 1. Static Routing

• Fixed routes

• Manually configured

• Used in small networks

---

🔹 2. Dynamic Routing

• Routes change automatically

• Uses routing algorithms

---

6️⃣ Routing Algorithms

---

🔹 1. Distance Vector Routing

Features:

• Based on distance and direction

• Uses Bellman-Ford algorithm

Example:

RIP (Routing Information Protocol)

---

Problems:

❌ Count to infinity
❌ Slow convergence

---

🔹 2. Link State Routing

Features:

• Each node knows full topology

• Uses Dijkstra’s algorithm

Example:

OSPF (Open Shortest Path First)

---

Advantages:

✔ Fast
✔ Accurate

---

7️⃣ Congestion Control

✅ Definition

Congestion occurs when:

Network traffic exceeds capacity.

---

Causes:

• Too many packets

• Limited bandwidth

• Slow routers

---

Congestion Control Techniques:

---

🔹 Open Loop

• Prevent congestion

• No feedback

Examples:
✔ Traffic shaping
✔ Admission control

---

🔹 Closed Loop

• Detect & correct congestion

• Uses feedback

Examples:
✔ Backpressure
✔ Choke packet

---

8️⃣ Internetworking

Definition:

Connecting multiple networks together to form the Internet.

---

Devices Used:

• Router

• Gateway

• Bridge

---

9️⃣ Internet Protocol (IP)

✅ IP

Responsible for:

• Logical addressing

• Packet delivery

---

🔹 IPv4 Address

• 32-bit address

• Written in dotted decimal

• Example: 192.168.1.1

---

IPv4 Classes

Class	Range
A	1–126
B	128–191
C	192–223
D	Multicast
E	Experimental

---

🔹 IPv6

Features:

✔ 128-bit address
✔ Larger address space
✔ Better security
✔ No NAT needed

---

Example:

2001:0db8:85a3::8a2e:0370:7334

---

🔟 Difference Between IPv4 and IPv6

IPv4	IPv6
32-bit	128-bit
Limited addresses	Large address space
NAT required	No NAT
Less secure	More secure

---

📌 EXAM IMPORTANT QUESTIONS (UNIT 3)

✔ Explain Network Layer
✔ Routing algorithms
✔ Difference between distance vector & link state
✔ Congestion control
✔ IPv4 vs IPv6
✔ IP addressing