Highly Important Questions

1.​ Convert the given NDFA to its equivalent DFA.

2.​ Construct the finite automaton equivalent to the regular expression (0+1)*(00+11).
3.​ Explain the role of Finite Automata and Regular Expression in Compiler Design.
4.​ Explain the working of Pushdown Automata with mathematical description.
5.​ What are NP-complete and NP-hard problems? In which category does Hamiltonian path
problem and Traveling Salesman problem lie and why?
6.​ Explain the following joins with help of examples: Theta join, Equi Join, Natural join,
Outer join.
7.​ How do triggers help in DBMS? Write a trigger in SQL to confirm the value inserted in
the age field of a table is not less than 18 before inserting the value.
8.​ Using a precedence graph, find out whether the schedule of three transactions T1, T2,
T3 is conflict serializable.
9.​ Explain primary key, candidate key, super key, and foreign key with examples.

Medium Importance Questions

11.​Design a Mealy Machine that computes 2’s complement of the given input binary
number.
12.​Write regular expressions (R) for the given conditions (Σ = {a, b}):
○​ (a) At least 3 characters
○​ (b) Every 'a' must be followed by 'b'
○​ (c) Second symbol from RHS is 'a'
○​ (d) At most two 'b's in the string
13.​Convert the following Context-Free Grammar (CFG) into an equivalent CFG in Chomsky
Normal Form.
14.​Design a Pushdown Automaton (PDA) accepting (a²bcⁿ, m,n ≥1) by null store.
15.​Give five examples of languages that cannot be accepted by Finite Automata but can be
accepted by Pushdown Automata. Contrast the reasons behind it.
16.​Explain the difference between Deterministic and Non-Deterministic Pushdown
Automata.
17.​State and explain the Pumping Lemma for regular sets. Prove whether the given
expression is regular or not using Pumping Lemma.
18.​Explain the Traveling Salesman problem in detail.

Low Importance Questions

20.​Recursive Language vs. Recursively Enumerable Languages – Differences & Examples.

21.​Properties of Context-Free Grammar (CFG) and Closure Rules.
22.​Variations of Turing Machines (Multi-Tape TM, Non-Deterministic TM, Universal TM) and
their significance.
23.​Explain the working of Pushdown Automata using a transition graph.
24.​Difference between FA & Transition Graph Acceptance.
25.​Explain DBMS Triggers & Write an SQL Constraint for Age Validation.
Highly Important Questions - Answers

1. Convert the given NDFA to its equivalent DFA

That’s a solid breakdown of the NDFA to DFA conversion process! 🔄

To further refine it, here's the stepwise approach with a transition table representation:

✅ Step 1: Identify NDFA States & Transitions

Given NDFA:​
| State | Input 0 | Input 1 |​
|----------|------------|------------|​
| q0 | q1 | — |​
| q1 | q1, q2 | q1 |​
| q2 | q2 | q2 |

✅ Step 2: Construct DFA States

The DFA states are combinations of NDFA states:

●​ Q0 → {q0}
●​ Q1 → {q1}
●​ Q2 → {q1, q2}

Now, defining DFA transitions:​

| DFA State | Input 0 | Input 1 |​
|--------------|------------|------------|​
| Q0 {q0} | Q1 {q1} | — |​
| Q1 {q1} | Q2 {q1, q2} | Q1 {q1} |​
| Q2 {q1, q2} | Q2 {q1, q2} | Q2 {q1, q2} |

✅ Step 3: Minimize DFA (if needed)

Since no unreachable states exist, we can finalize the DFA transition graph

2. Construct the finite automaton equivalent to the regular expression (0+1)*(00+11)

Here's the finite automaton for the given regular expression (0+1)*(00+11), ensuring it correctly
tracks sequences ending in "00" or "11":
✅ Regular Expression Breakdown:
●​ (0+1)* → Accepts any sequence of 0s and 1s.
●​ (00+11) → Ensures final characters match either "00" or "11".

✅ Finite Automaton Construction Steps:

1.​ Initial state (q0): Accepts any sequence of 0s and 1s.
2.​ Intermediate states (q1, q3): Tracks first 0 or 1 for ending sequence.
3.​ Final state (q2, q4): Ensures correct termination with "00" or "11".

✅ Transition Table Representation:

Current State Input Next State

q0 0 q1

q0 1 q3

q1 0 q2 (Accept)

q3 1 q4 (Accept)

q2/q4 (Final) —

✅ Final states: {q2, q4} ensure acceptance.

3. Explain the role of Finite Automata and Regular Expression in Compiler Design

✅ Finite Automata (FA) in Compilers:

1.​ Lexical Analysis:​

○​ Converts source code into tokens (keywords, identifiers, operators).

 ○​ Example: FA recognizes numbers, variables, and reserved words in code.
2.​ Syntax Parsing:​

○​ Helps construct Abstract Syntax Trees (ASTs) for grammatical correctness.

○​ Example: Parsing arithmetic expressions like (x + y) * z.
3.​ Pattern Matching:​

○​ Used in search engines, text editors, and spam filters.

○​ Example: FA finds occurrences of specific patterns in large datasets.

✅ Regular Expressions (Regex) in Compilers:

1.​ Token Definition:​

○​ Regex defines lexical rules (keywords, numbers, symbols).

○​ Example: Regex ^[a-zA-Z]+$ matches valid variable names.
2.​ Simplifies Scanning Algorithms:​

○​ Regex allows compact representations of language rules.

○​ Example: Matching floating-point numbers using \d+\.\d+.

Finite Automata and Regular Expressions streamline compiler processes, ensuring efficient
token recognition, pattern matching, and syntax validation.

4. Explain the working of Pushdown Automata with mathematical description

Pushdown Automata (PDA) – Working & Mathematical Description

✅ Pushdown Automata Components:

●​ States: Includes initial state (q₀) and accepting state (q_accept).
●​ Stack Operations:
○​ Push: Stores symbols onto the stack.
○​ Pop: Removes symbols when processed.
●​ Transitions: Moves between states based on input & stack contents.

✅ Mathematical Definition:​
A PDA is defined as (Q, Σ, Γ, δ, q₀, F) where:

●​ Q → Set of states {q₀, q₁, q_accept}.

●​ Σ → Input alphabet {a, b}.
●​ Γ → Stack alphabet {A, Z₀} (where Z₀ is the initial stack symbol).
 ●​ δ → Transition function {current_state, input_symbol, stack_top} →
{next_state, stack_action}.
●​ q₀ → Initial state.
●​ F → Final (accepting) state.

✅ Example: PDA for L = {aⁿbⁿ | n ≥ 0}

1.​ Push 'A' onto the stack for each 'a' → Tracks occurrences of 'a'.
2.​ Pop 'A' for each 'b' → Ensures equal 'a's and 'b's.
3.​ Accept if stack is empty at the end → Confirms balanced input.

✅ Transitions:​
| Current State | Input | Stack Top | Next State | Stack Action |​
|------------------|----------|-------------|--------------|---------------|​
| q₀ | a | Z₀ | q₁ | Push A |​
| q₁ | a | A | q₁ | Push A |​
| q₁ | b | A | q₂ | Pop A |​
| q₂ | b | A | q₂ | Pop A |​
| q₂ | ε | Z₀ | q_accept | No action |

5. What are NP-complete and NP-hard problems? In which category does Hamiltonian
path problem and Traveling Salesman problem lie and why?

NP-Complete and NP-Hard Problems

✅ NP-Complete Problems:
●​ Belong to class NP (Nondeterministic Polynomial time).
●​ Can be verified quickly (in polynomial time) but solving them efficiently is hard.
●​ Every NP-complete problem is at least as hard as the hardest problems in NP.
●​ Example: Hamiltonian Path Problem.

✅ NP-Hard Problems:
●​ Do not necessarily belong to NP but are at least as hard as the hardest NP problems.
●​ Difficult to solve AND verify in polynomial time.
●​ A solution to any NP-hard problem could be used to solve all NP problems
efficiently.
●​ Example: Traveling Salesman Problem (TSP).
🔹 Hamiltonian Path Problem (HP) → NP-Complete
●​ Given a graph, verifying if a Hamiltonian path exists is polynomial-time solvable,
but finding the path requires exponential time.

🔹 Traveling Salesman Problem (TSP) → NP-Hard

●​ Finding the shortest route visiting all cities is computationally expensive, and verifying
the solution itself requires high computation.

6. Explain the following joins with help of examples: Theta join, Equi Join, Natural join,
Outer join

Different Types of SQL Joins with Examples

✅ Theta Join:​
A Theta Join applies a general condition (θ) between attributes of two tables.

SELECT * FROM Employee e, Department d WHERE e.dept_id < d.dept_id;

Example: Find employees whose department ID is less than another department’s ID.

✅ Equi Join:​
An Equi Join applies an equality condition (=) between attributes.

SELECT * FROM Employee e JOIN Department d ON e.dept_id = d.dept_id;

Example: Match employees with their corresponding department using dept_id.

✅ Natural Join:​
A Natural Join automatically matches columns with the same name in both tables.

SELECT * FROM Employee NATURAL JOIN Department;

Example: If both tables have a common column dept_id, SQL automatically joins them.

✅ Outer Join:​
An Outer Join returns matching rows AND unmatched rows from one or both tables.

SELECT * FROM Employee e LEFT JOIN Department d ON e.dept_id = d.dept_id;

Example: Return all employees, even if they don’t belong to a department.

7. How do triggers help in DBMS? Write a trigger in SQL to confirm the value inserted in
the age field of a table is not less than 18 before inserting the value.

Triggers in DBMS – Purpose & Example

✅ Role of Triggers in DBMS:

●​ Enforces Data Integrity: Ensures that constraints like age limits or salary restrictions
are maintained.
●​ Automates Updates & Validations: Eliminates manual error-checking by running
predefined conditions on data modifications.
●​ Enhances Security: Prevents unauthorized changes by enforcing business rules at the
database level.

✅ SQL Trigger Example

This trigger ensures that no user can insert an age less than 18 into the Users table.

CREATE TRIGGER age_check

BEFORE INSERT ON Users
FOR EACH ROW
BEGIN
IF NEW.age < 18 THEN
SIGNAL SQLSTATE '45000'
SET MESSAGE_TEXT = 'Age must be at least 18';
END IF;
END;

✅ How It Works:
1.​ The trigger activates before inserting a new row into the Users table.
2.​ Checks if NEW.age (inserted value) is less than 18.
3.​ If the condition is true, the database throws an error message, preventing the insertion.

8. Using a precedence graph, find out whether the schedule of three transactions T1, T2,
T3 is conflict serializable.

Conflict Serializability Using Precedence Graph

✅ Definition:​
A schedule is conflict serializable if its precedence graph has NO cycles.

✅ Step 1: Identify Transactions & Operations

Transac Opera Data
tion tio Ite
n m

T1 Read( X
X)

T1 Write( X
X)

T2 Read( Y
Y)

T2 Write( Y
Y)

T3 Read( X
X)

T3 Write( Y
Y)

✅ Step 2: Identify Conflict Dependencies

Types of Conflicts:

1.​ Write-Read (W-R) Conflict:​

○​ T1 writes X, later T3 reads X → Edge from T1 → T3.

 2.​ Write-Write (W-W) Conflict:​

○​ T3 writes Y, after T2 writes Y → Edge from T3 → T2.

✅ Step 3: Construct Precedence Graph

Dependency Edge in
Type Graph

W-R Conflict T1 → T3
on X

W-W Conflict T3 → T2
on Y

✅ Step 4: Check for Cycles

✅
●​ The precedence graph contains edges T1 → T3 and T3 → T2.
●​ No cycle detected, meaning the schedule is conflict serializable.

9. Explain primary key, candidate key, super key, and foreign key with examples.

Keys in Database Management System (DBMS)

✅ Primary Key:
●​ A column or a set of columns that uniquely identifies each row in a table.
●​ No duplicate values allowed and cannot be NULL.

Example:

CREATE TABLE Students (

ID INT PRIMARY KEY,
Name VARCHAR(50)
);
Here, ID uniquely identifies every student.

✅ Candidate Key:
●​ A set of attributes that can be a primary key, but only one is selected.
●​ Can have multiple candidate keys in a table, but only one primary key.

Example:​
If both ID and Roll_No are unique:

(ID, Roll_No) → Candidate Keys

Either ID or Roll_No can be made the primary key.

✅ Super Key:
●​ Any set of attributes that contains a candidate key.
●​ May have extra attributes but still uniquely identifies rows.

Example:

(ID, Name) → Super Key

Even if Name is redundant, ID ensures uniqueness.

✅ Foreign Key:
●​ A column in one table that refers to the primary key of another table.
●​ Ensures referential integrity in relational databases.

Example:

CREATE TABLE Orders (

OrderID INT,
CustomerID INT,
FOREIGN KEY (CustomerID) REFERENCES Customers(ID)
);

Here, CustomerID links to ID in the Customers table.

Medium Importance Questions

1. Design a Mealy Machine that Computes 2’s Complement of a Binary

Number

Mealy Machine for Computing 2’s Complement of a Binary Number

✅ Mealy Machine Characteristics:

●​ In a Mealy machine, the output depends on both the current state and input.
●​ To compute 2’s complement, we flip bits after the first '1' from the right.

✅ State Transitions:
State Input Output Next State

q0 0 0 q0

q0 1 1 q1

q1 0 1 q1

q1 1 0 q1

✅ Working Principle:
1.​ Start in q0 (initial state) → No modification to input.
2.​ Move to q1 when encountering the first '1' → Flip all subsequent bits.
3.​ Continue flipping in q1 state for remaining bits.
2. Write Regular Expressions (R) for Given Conditions (Σ = {a, b})

Regular Expressions (R) for Given Conditions (Σ = {a, b})

✅ (a) At least 3 characters:

R = (a+b)(a+b)(a+b)*

●​ Ensures the string contains at least three characters (a or b).

●​ Accepts strings like "aaa", "abb", "babaa".

✅ (b) Every 'a' must be followed by 'b':

R = (ab)*

●​ Ensures every occurrence of 'a' is immediately followed by 'b'.

●​ Accepts strings like "ab", "abab", "ababab".

✅ (c) Second symbol from RHS is 'a':

R = (a+b)*a(a+b)

●​ Ensures the second last character in the string is always 'a'.

●​ Accepts strings like "ba", "baba", "aaa".

✅ (d) At most two 'b's in the string:

R = (a*ba*ba*) | (a*)

●​ Allows a maximum of two occurrences of 'b', while allowing any number of 'a's.
●​ Accepts strings like "a", "ab", "aba", "aabab", "aaa".
3. Convert the Given CFG into Chomsky Normal Form (CNF)

✅ Steps for CNF Conversion:

1.​ Eliminate Null (ε) Productions → Remove nullable variables.
2.​ Eliminate Unit Productions (A → B) → Replace with direct terminals.
3.​ Ensure Each Rule Has At Most Two Symbols → Convert long productions.

✅ Example CFG:
S → AB
A→a|ε
B → BC | b
C→c

✅ Step 1: Eliminate Null (ε) Productions​

Since A → ε, we replace occurrences of A in S → AB:

S → AB | B
A→a
B → BC | b
C→c

✅ Step 2: Eliminate Unit Productions (B → C)​

Replace B → C with B → c:

S → AB | B
A→a
B → Xb
X→ε|C
C→c

✅ Step 3: Convert to CNF (Max Two Symbols Per Rule)​

Final CNF conversion ensures binary productions only:

S → AB | B
A→a
B → Xb
X→C
C→c
4. Design a Pushdown Automaton (PDA) Accepting L = (a²bcⁿ, m,n ≥1) by
Null Store

Pushdown Automaton (PDA) Accepting L = (a²bcⁿ, m,n ≥1) by Null Store

✅ PDA Construction:
●​ Push 'A' for each 'a' onto the stack to track occurrences of 'a'.
●​ Transition after reading 'b' – signifies a shift in input processing.
●​ Pop 'A' for each 'c' to verify correct balancing of symbols.

✅ Transition Table Representation:

State Input Stack Top Next State Stack
Action

q0 a Z₀ q1 Push A

q1 a A q1 Push A

q1 b A q2 No Action

q2 c A q2 Pop A

q2 ε Z₀ q_accept No Action

Explanation:

●​ The PDA starts at q0 and pushes 'A' onto the stack for each 'a' encountered.
●​ When 'b' is read, it moves to q2 without altering the stack.
●​ For each 'c', an 'A' is popped, ensuring valid sequences.
●​ If the stack is empty after reading all 'c's, the PDA accepts the input.
5. Five Examples of Languages Not Acceptable by Finite Automata but by
PDA

Finite Automata (FA) lack memory, making them incapable of recognizing languages
requiring recursive tracking or stack operations. Pushdown Automata (PDA), with their
stack-based memory, can recognize many such languages.

✅ Examples of Languages Recognizable by PDA but Not FA:

1.​ Balanced Parentheses Language (L = { (ⁿ)ⁿ })​

○​ Example: "((()))"
○​ Why FA Fails: FA cannot track nested parentheses since it lacks a stack.
○​ Why PDA Works: PDA pushes ( onto the stack and pops ) when encountered.
2.​ Palindrome Language (L = { wwᵀ })​

○​ Example: "abba", "racecar"

○​ Why FA Fails: FA cannot store half the string for later comparison.
○​ Why PDA Works: PDA pushes the first half onto the stack and matches it with
the second half.
3.​ L = { aⁿbⁿcⁿ | n ≥ 1 }​

○​ Example: "aaabbbccc"
○​ Why FA Fails: FA cannot track all three symbols with equal occurrences.
○​ Why PDA Works: PDA pushes as, transitions for bs, and pops cs for validation.
4.​ Duplicate Word Language (L = { ww | w ∈ {a, b} })*​

○​ Example: "abababab"
○​ Why FA Fails: FA cannot store w to check repetition.
○​ Why PDA Works: PDA stores w and verifies the second occurrence.
5.​ Context-Free Grammar-Based Languages​

○​ Example: Programming languages, nested expressions

○​ Why FA Fails: FA cannot process recursive grammatical structures.
○​ Why PDA Works: PDA can handle recursive and nested expressions, essential
for syntax checking in compilers.

6. Difference Between Deterministic & Non-Deterministic Pushdown

Automata
 Feature Deterministic PDA Non-Deterministic PDA (ND-PDA)
(D-PDA)

Transitions One unique transition per Multiple possible transitions for the
input and stack same input
symbol

Behavior Predictable and follows a Uses guessing and multiple paths

single path to find acceptance

Acceptance Must reach a final state Can take multiple paths and may
Mechanis with an empty stack reach an accepting state
m through any path

Computational Less powerful than More powerful due to multiple

Power ND-PDA transition choices

Example L = { aⁿbⁿ } (Equal 'a's and L = { wwᵀ } (Palindromes)

Language 'b's)

Usage Used for simpler Used for complex context-free

context-free languages like palindromes
languages

Efficiency Requires exact rules and Faster for problems where guessing
structured transitions helps, but may require more
computation

Limitations Cannot recognize some Can recognize more complex

languages (e.g., patterns using multiple paths
palindromes)
✅ Key Takeaway:
●​ D-PDA is more structured but less powerful.
●​ ND-PDA can handle more complex languages, making it more flexible but
computationally expensive.

7. Pumping Lemma for Regular Sets (Proof Example)

✅ Definition:​
The Pumping Lemma states that if a language L is regular, then any sufficiently long string in
L can be decomposed into three parts (xyz) such that:

1.​ y ≠ ε (y must not be empty).

2.​ |xy| ≤ p (where p is the pumping length).
3.​ xyⁿz ∈ L for all n ≥ 0 (We can repeat y any number of times, and the resulting string
remains in L).

✅ Example: Proving L = { aⁿbⁿ | n ≥ 1 } is NOT Regular

Step 1: Assume L is Regular

●​ Suppose L = { aⁿbⁿ | n ≥ 1 } is regular.

●​ By Pumping Lemma, there exists a pumping length (p) for L.

Step 2: Choose a String

●​ Select a string s from L, s = "aaaaabbbbb" (where n = 5).

●​ This string is longer than pumping length p, so it must be pumpable.

Step 3: Divide s into xyz

●​ Decompose "aaaaabbbbb" into xyz, ensuring:

○​ x = "aaa"
○​ y = "a" (|y| > 0)
○​ z = "aabbbbb"

Step 4: Pump y (Repeat y)

●​ Repeat y for n = 2:
○​ Resulting string: "aaaaaaabbbbb"
●​ This breaks the pattern (number of 'a's does not match 'b's).

Step 5: Contradiction
 ●​ "aaaaaaabbbbb" is not in L, meaning L cannot be regular.
●​ Contradiction → L is NOT regular .✅
Since L fails the Pumping Lemma, it is not a regular language.

8. Explain the Traveling Salesman Problem (TSP)

Traveling Salesman Problem (TSP) – Explanation

✅ Definition:
●​ The Traveling Salesman Problem (TSP) involves finding the shortest possible route
that allows a salesman to visit every city once and return to the starting city with
minimal cost.

✅ Computational Complexity:
●​ TSP is classified as an NP-hard problem, meaning no known polynomial-time
solution exists.
●​ Exponential time complexity makes solving TSP efficiently challenging as the number
of cities grows.

✅ Approaches to Solve TSP:

Method Description Complexity

Brute Force Tests all possible routes O(n!) (Extremely

exhaustively slow)

Dynamic Breaks the problem into O(n²2ⁿ) (Better

Programming subproblems and uses than brute
(Held-Karp memoization force)
Algorithm)

Approximation Heuristics like Nearest Neighbor, Polynomial time

Algorithms Genetic Algorithms, and (Efficient but
Simulated Annealing not optimal)
✅ Real-World Applications:
●​ Logistics & Supply Chain Management – Optimizing delivery routes for couriers &
shipping.
●​ Network Routing – Efficient path selection in communication networks.
●​ Manufacturing & Robotics – Determining the optimal movement sequence for robotic
arms.
●​ Tour Planning – Finding optimal sightseeing routes in cities.