chapter

Finite Automata and Regular Expressions Short Notes for GATE CS

Finite Automata and Regular Expressions short notes for GATE CS: 5 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice que

finite automata and regular expressions short notes

Quick Revision: NFA to DFA Checklist

@keyframes checkIn { 0% { opacity: 0.5; transform: translateX(-10px); } 100% { opacity: 1; transform: translateX(0); } } .check-item { display: flex; align-items: flex-start; gap: 12px; margin-bottom: 12px; padding: 12px; background: color-mix(in srgb, var(--color-muted), transparent 92%); border-radius: 6px; opacity: 0; animation: checkIn 0.5s ease-out forwards; } .check-item:nth-child(2) { animation-delay: 0.1s; } .check-item:nth-child(3) { animation-delay: 0.3s; } .check-item:nth-child(4) { animation-delay: 0.5s; } .check-item:nth-child(5) { animation-delay: 0.7s; } .check-item:nth-child(6) { animation-delay: 0.9s; } .check-item:nth-child(7) { animation-delay: 1.1s; } .check-icon { width: 20px; height: 20px; flex-shrink: 0; border: 2px solid var(--color-primary); border-radius: 4px; display: flex; align-items: center; justify-content: center; margin-top: 2px; } .check-icon::after { content: ''; width: 10px; height: 5px; border-left: 2px solid var(--color-primary); border-bottom: 2px solid var(--color-primary); transform: rotate(-45deg) translateY(-2px); } NFA to DFA Conversion Checklist Start State: DFA start state equals the epsilon-closure of the NFA start state. Transitions: For state S and symbol a, next state equals the epsilon-closure of the union of transitions from all states in S on input a . Final States: DFA state S is final if S contains at least one NFA final state. State Bound: Maximum possible DFA states equals 2^{n}, where n is the number of NFA states. Dead State: The empty set \emptyset is a valid state and must be counted if the DFA requires a total transition function. Equivalence: The resulting DFA accepts the exact same language as the original NFA.

Quick Revision: Minimization Checklist

@keyframes checkIn { 0% { opacity: 0.5; transform: translateX(-10px); } 100% { opacity: 1; transform: translateX(0); } } .check-item { display: flex; align-items: flex-start; gap: 12px; margin-bottom: 12px; padding: 12px; background: color-mix(in srgb, var(--color-muted), transparent 92%); border-radius: 6px; opacity: 0; animation: checkIn 0.5s ease-out forwards; } .check-item:nth-child(2) { animation-delay: 0.1s; } .check-item:nth-child(3) { animation-delay: 0.3s; } .check-item:nth-child(4) { animation-delay: 0.5s; } .check-item:nth-child(5) { animation-delay: 0.7s; } .check-item:nth-child(6) { animation-delay: 0.9s; } .check-item:nth-child(7) { animation-delay: 1.1s; } .check-item:nth-child(8) { animation-delay: 1.3s; } .check-icon { width: 20px; height: 20px; flex-shrink: 0; border: 2px solid var(--color-primary); border-radius: 4px; display: flex; align-items: center; justify-content: center; margin-top: 2px; } .check-icon::after { content: ''; width: 10px; height: 5px; border-left: 2px solid var(--color-primary); border-bottom: 2px solid var(--color-primary); transform: rotate(-45deg) translateY(-2px); } DFA Minimization Checklist Step 1: Remove all unreachable states via BFS/DFS from the start state. Step 2: Create a table of all state pairs (p, q) . Step 3: Mark all pairs where one state is final and the other is non-final. Step 4: Iteratively mark (p, q) if \exists a \in Σ such that (δ (p, a), δ (q, a)) is already marked. Step 5: Stop when a full pass yields no new marks. Step 6: Merge all unmarked pairs into single states. Step 7: Verify the new DFA is deterministic, complete, and has no unreachable states.

Revision Checklist: Counting and Divisibility

Revision Checklist: Counting and Divisibility 1. String Counting Protocol Calculate total universe: \sum_{i = 0}^{n} ∣Σ ∣^{i} . Evaluate regex length-by-length (0, 1, 2, \dots, n). Use set union (∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣) to avoid double-counting. Subtract from universe if the question asks for "neither" or "complement". 2. Divisibility by k (Binary, MSB first) DFA has k states (q_{0} to q_{k - 1}). Transition: δ (q_{r}, b) = q_{(2 r + b) mod k} . Canonical Regex for k = 3 : (0 + 1 (0 1^{*} 0)^{*} 1)^{*} . ϵ is always accepted (value 0). Leading zeros are naturally accepted unless explicitly forbidden. 3. Regex Decoding Shortcuts One a in prefix + even a's in star ⟹ Odd number of a's. Pairs of 1's separated by anything ⟹ Even number of 1's.

2 more cards in this chapter

Free preview ends here

Login to view the complete short notes

Creating an account is free. You get the rest of this chapter, step-by-step solutions, and a study plan built around the topics you are actually weak at.

Why MastersUp

Personalised first. High quality throughout.

Most platforms hand everyone the same content. Here the content moves with your performance, topic by topic.

Built around you, not around a syllabus PDF

Every answer you give moves your topic-level intelligence rate. The next question, the next revision card and tomorrow's plan all change with it.

Revision that hits your weak spots

We only revise topics you have actually attempted and are still below the safe bar on — never the same chapter on repeat.

Questions calibrated to the real exam

Each question carries a measured toughness. You are served a rung above your current level, so practice keeps stretching you.

Notes written for recall, not for volume

Full lesson cards for first study, curated short-note cards for the last mile — with derivations, traps and exam patterns marked.

One place for everything

Notes, chapter practice, previous-year questions, test series and full-length papers — all feeding one picture of your preparation.

Honest progress

No vanity streaks. Progress here means chapters mastered and accuracy that held up on harder questions.

Unlock the whole course

Full notes and short notes, the complete question bank with worked solutions, mock tests, full-length papers, and an adaptive plan that rebuilds itself as you improve.

View all plans Start free

Finite Automata and Regular Expressions Short Notes for GATE CS

Finite Automata and Regular Expressions short notes for GATE CS: 5 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

Quick Revision: NFA to DFA Checklist

NFA to DFA Conversion Checklist

Start State: DFA start state equals the epsilon-closure of the NFA start state.

Transitions: For state

S

and symbol

a

, next state equals the epsilon-closure of the union of transitions from all states in

S

on input

a

Final States: DFA state

S

is final if

S

contains at least one NFA final state.

State Bound: Maximum possible DFA states equals

2^{n}

, where

n

is the number of NFA states.

Dead State: The empty set

\emptyset

is a valid state and must be counted if the DFA requires a total transition function.

Equivalence: The resulting DFA accepts the exact same language as the original NFA.

Quick Revision: Minimization Checklist

DFA Minimization Checklist

Step 1: Remove all unreachable states via BFS/DFS from the start state.

Step 2: Create a table of all state pairs

(p, q)

Step 3: Mark all pairs where one state is final and the other is non-final.

Step 4: Iteratively mark

(p, q)

\exists a \in Σ

such that

(δ (p, a), δ (q, a))

is already marked.

Step 5: Stop when a full pass yields no new marks.

Step 6: Merge all unmarked pairs into single states.

Step 7: Verify the new DFA is deterministic, complete, and has no unreachable states.

Revision Checklist: Counting and Divisibility

1. String Counting Protocol

Calculate total universe: $\sum_{i = 0}^{n} ∣Σ ∣^{i}$ .
Evaluate regex length-by-length ( $0, 1, 2, \dots, n$ ).
Use set union ( $∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣$ ) to avoid double-counting.
Subtract from universe if the question asks for "neither" or "complement".

2. Divisibility by $k$ (Binary, MSB first)

DFA has $k$ states ( $q_{0}$ to $q_{k - 1}$ ).
Transition: $δ (q_{r}, b) = q_{(2 r + b) mod k}$ .
Canonical Regex for $k = 3$ : $(0 + 1 (0 1^{*} 0)^{*} 1)^{*}$ .
$ϵ$ is always accepted (value 0).
Leading zeros are naturally accepted unless explicitly forbidden.

3. Regex Decoding Shortcuts

One $a$ in prefix + even $a$ 's in star $⟹$ Odd number of $a$ 's.
Pairs of $1$ 's separated by anything $⟹$ Even number of $1$ 's.

Revision Checklist: FA to Regex Conversion

1. Arden's Theorem Protocol

Write equations for all states: $q_{i} = \sum (q_{j} \cdot label) + (ϵ if start)$ .
Substitute non-start states into the start state equation.
Apply $R = Q + R P ⟹ R = Q P^{*}$ to solve.

2. State Elimination (GNFA) Checklist

Ensure exactly one start state (no incoming edges) and one final state (no outgoing edges).
Eliminate intermediate states one by one.
Update edges: $R_{n e w} = R_{o l d} + R_{in, r i p} (R_{r i p, r i p})^{*} R_{r i p, o u t}$ .

3. Final Verification

Does the regex accept $ϵ$ if the start state is final?
Test the derived regex with 2-3 short strings accepted by the original FA.

finite automata and regular expressions short notes

Quick Revision: NFA to DFA Checklist

NFA to DFA Conversion Checklist

Quick Revision: Minimization Checklist

DFA Minimization Checklist

Revision Checklist: Counting and Divisibility

Revision Checklist: Counting and Divisibility

1. String Counting Protocol

2. Divisibility by k (Binary, MSB first)

3. Regex Decoding Shortcuts

Login to view the complete short notes

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course

Finite Automata and Regular Expressions Short Notes for GATE CS

Quick Revision: NFA to DFA Checklist

NFA to DFA Conversion Checklist

Quick Revision: Minimization Checklist

DFA Minimization Checklist

Revision Checklist: Counting and Divisibility

Revision Checklist: Counting and Divisibility

1. String Counting Protocol

2. Divisibility by k (Binary, MSB first)

3. Regex Decoding Shortcuts

Revision Checklist: FA to Regex Conversion

Revision Checklist: FA to Regex Conversion

1. Arden's Theorem Protocol

2. State Elimination (GNFA) Checklist

3. Final Verification

More short notes in this unit

2. Divisibility by $k$ (Binary, MSB first)

2. Divisibility by $k$ (Binary, MSB first)