Primers

ACompressed recap

🧾

Strings and languages: alphabet Σ, strings, ε, concatenation, prefixes (n + 1 of them), languages as sets of strings, union/intersection/difference, L*. Regular expressions describe languages with ε, symbols, |, concatenation and ; precedence * > · > |; regular definitions name parts (id → letter(letter|digit)). Finite automata recognise the same languages: DFA (one move per state and symbol) and NFA (choices and ε-moves); subset construction turns an NFA into a DFA (≤ 2ⁿ states). Data structures: stack (LIFO), tree (pre/postorder), hash table (k mod m, chaining), directed graph and DAG.

BMerged rule card

0.2.1 Alphabets, strings, languages; sets, union, intersection

• Alphabet Σ: finite set of symbols. String: finite sequence; |w| its length; ε has length 0.
• Concatenation xy; εw = w.
• Length-n string: n + 1 prefixes, n + 1 suffixes; n(n+1)/2 non-empty substrings if symbols distinct.
• Language = set of strings ⊆ Σ*. ∅ ≠ {ε}.
• LM = {xy}; L* = {ε} ∪ L ∪ LL ∪ …; L⁺ = LL*.
• Sets: ∪, ∩, −; |A ∪ B| = |A| + |B| − |A ∩ B|.

0.2.2 Regular expressions (what lexical analysis needs)

• Building blocks: ε, a, r|s, rs, r*, (r).
• Precedence: * > concatenation > |.
• Shorthands: r+ = rr*, r? = r|ε, [a-z], [0-9].
• id → letter (letter | digit)*; number → digits (. digits)? (E [+-]? digits)?
• (a|b)* = (ab); (r)* = r*.
• Cannot count without limit (balanced brackets).

0.2.3 Finite automata: DFA, NFA and the idea of converting NFA to DFA

• DFA (Q, Σ, δ, q₀, F): one move per state and symbol; accept if the run ends in F.
• NFA: sets of next states, ε-moves; accept if some path ends in F.
• NFA ≡ DFA in power (same languages).
• Subset construction: start = ε-closure({q₀}); next = ε-closure(moves on a); at most 2ⁿ states.
• Regular expression → NFA (Thompson) → DFA → minimal DFA: the lexer’s pipeline.

0.2.4 Data structures: stack, tree, hash table, directed graph

• Stack: push/pop/top, LIFO.
• Tree: root, parent, children, leaves; height = longest root-to-leaf path in edges.
• Preorder: node, then children. Postorder: children, then node.
• Hash table: h(k) = k mod m; collisions handled by chaining; average O(1) lookup → symbol tables.
• Directed graph: nodes, edges u → v, successors/predecessors, paths, cycles; DAG = no cycle.

CInterleaved GATE-style questions

Q1NAT1 markStrings

How many suffixes (including ε and the string itself) does lexer have?

Numerical answer: ________

Q2MCQ1 markRegex

Which string is in L((ab|b)*a)?

• (A) ab
• (B) aba
• (C) abb
• (D) bb

Q3NAT2 marksRegex counting

How many strings of length 5 over {0, 1} begin with 1 and end with 0?

Numerical answer: ________

Q4MSQ1 markAutomata

Which are true?

• (A) Subset construction always produces a DFA with exactly 2ⁿ states.
• (B) ε-closure must be applied after each move when an NFA has ε-moves.
• (C) A DFA accepts a string if its run ends in an accepting state.
• (D) Every regular expression can be turned into an NFA.

Q5MCQ1 markStack

Pushing 1, 2, 3, 4 in that order (pops may happen in between), which pop sequence is impossible?

• (A) 4 3 2 1
• (B) 1 2 3 4
• (C) 3 1 2 4
• (D) 2 1 4 3

Q6NAT1 markTrees

A tree has a root with 3 children; each child has 2 children, which are leaves. How many leaves does it have?

Numerical answer: ________

Q7MCQ2 marksSubset construction

An NFA over {a} has states 0 (start) and 1 (accepting) with moves 0 –a→ {0, 1} and 1 –a→ ∅. The DFA from subset construction accepts:

• (A) only the string a
• (B) all strings of one or more a’s
• (C) ε and all strings of a’s
• (D) no strings

Q8MSQ2 marksSets and languages

Let L = {a, b}. Which are true?

• (A) |LL| = 4
• (B) ε ∈ L*
• (C) L⁺ contains ε
• (D) LL ⊆ L*