How is the Pumping Lemma for regular languages used to prove that L = {0ⁿ1ⁿ | n ≥ 0} is not regular?

If L were regular with pumping length p, choose s = 0^p 1^p ∈ L. For any split s = xyz with |xy| ≤ p and |y| ≥ 1, y consists solely of 0s (y = 0^k, k ≥ 1). Pumping to xy²z = 0^{p+k}1^p yields unequal numbers of 0s and 1s, so xy²z ∉ L — a contradiction.

What is the Extended Binomial Series expansion for 1 / (1 − x)^k (k ≥ 1), and what is the coefficient of xⁿ?

1 / (1 − x)^k = Σ_{n=0}^∞ C(n + k − 1, n) xⁿ, so the coefficient [xⁿ] is C(n + k − 1, k − 1).

What is the Ordinary Generating Function (OGF) of a sequence {aₙ}, and what sequence corresponds to G(x) = 1 / (1 − cx)?

G(x) = Σ_{n=0}^∞ aₙ xⁿ. For G(x) = 1 / (1 − cx) = Σ_{n=0}^∞ cⁿ xⁿ, the sequence is aₙ = cⁿ.

What is a bipartite graph, and what is König's characterization of bipartite graphs in terms of cycles?

A graph whose vertex set V can be partitioned into two disjoint independent sets V₁ and V₂ such that every edge connects a vertex in V₁ to one in V₂. A graph is bipartite if and only if it contains no cycles of odd length.

What is the minimum height of a binary tree with l leaves, and why does this imply the Ω(n log n) lower bound for comparison-based sorting?

A binary tree of height h has at most 2^h leaves, so h ≥ ⌈log₂ l⌉. A comparison decision tree sorting n elements must have at least n! leaves, requiring worst-case height ≥ log₂(n!) = Θ(n log n).

State Kleene's Theorem connecting regular expressions and finite automata.

A formal language L ⊆ Σ* is regular (recognized by some DFA/NFA) if and only if it can be described by a regular expression built from ∅, ε, alphabet symbols, union (∪), concatenation (·), and Kleene star (*).

How is a second-order linear homogeneous recurrence relation aₙ = c₁ a_{n−1} + c₂ a_{n−2} solved using its characteristic equation?

Solve r² − c₁ r − c₂ = 0: - If roots r₁ ≠ r₂ are distinct: aₙ = α r₁ⁿ + β r₂ⁿ. - If there is a repeated root r₀: aₙ = (α + β n) r₀ⁿ.

What does the k-th power A^k of the adjacency matrix A of a graph G represent?

The entry (A^k)_{ij} equals the exact number of walks of length k from vertex vᵢ to vertex vⱼ in G.

How does a Hamiltonian cycle differ from an Eulerian circuit, and what do Dirac's and Ore's Theorems guarantee?

A Hamiltonian cycle visits every vertex exactly once (deciding existence is NP-complete, unlike Eulerian circuits). For a simple graph on n ≥ 3 vertices, Ore's Theorem guarantees a Hamiltonian cycle if deg(u) + deg(v) ≥ n for every non-adjacent pair u ≠ v, and Dirac's Theorem guarantees one if deg(v) ≥ n/2 for every vertex v.

What are the axioms of a Boolean Algebra (B, +, ·, ', 0, 1)?

With distinct elements 0 ≠ 1: Associative laws, Commutative laws, Identity laws (x + 0 = x, x · 1 = x), Distributive laws (x · (y + z) = (x · y) + (x · z) and x + (y · z) = (x + y) · (x + z)), and Complement laws (x + x' = 1, x · x' = 0).

How does a Nondeterministic Finite Automaton (NFA) differ from a DFA, and why do they recognize the exact same class of languages?

An NFA allows transition function δ: Q × (Σ ∪ {ε}) → P(Q) (multiple or zero next states and ε-transitions). By the Subset (Powerset) Construction, any k-state NFA can be converted into an equivalent DFA with at most 2^k states.

How do Kruskal's and Prim's greedy algorithms construct a Minimum Spanning Tree (MST)?

Kruskal's algorithm sorts all edges by weight and repeatedly adds the lightest edge that does not create a cycle (using Union-Find). Prim's algorithm grows a single connected tree from a starting vertex by repeatedly adding the cheapest edge crossing the cut.

What is the formula for the n-th Catalan number Cₙ, and what classic combinatorial structures does it count?

Cₙ = (1 / (n + 1)) C(2n, n). It counts balanced parentheses strings of length 2n, full binary trees with n + 1 leaves, Dyck paths from (0,0) to (2n,0), and triangulations of a convex (n + 2)-gon.

What is the difference between Disjunctive Normal Form (DNF) and Conjunctive Normal Form (CNF), and why is {NAND} functionally complete?

DNF is a disjunction (OR) of conjunctive terms (ANDs of literals; in full canonical DNF, a sum of minterms), whereas CNF is a conjunction (AND) of disjunctive clauses (ORs of literals; in full canonical CNF, a product of maxterms). {NAND} is functionally complete because NOT, AND, and OR can all be constructed using only NAND gates (e.g., ¬x = x NAND x).

State Hall's Marriage Theorem for bipartite graphs.

A bipartite graph G = (V₁, V₂, E) has a complete matching saturating every vertex of V₁ if and only if for every subset S ⊆ V₁, the neighborhood satisfies |N(S)| ≥ |S|.

What is graph isomorphism, and what are common graph invariants used to prove two graphs are NOT isomorphic?

Two graphs G₁ and G₂ are isomorphic if there is a bijection f: V(G₁) → V(G₂) preserving adjacency. Common invariants include vertex count, edge count, degree sequence, number of connected components, and lengths of simple cycles.

What is the recurrence relation and closed-form solution for the Tower of Hanoi puzzle with n disks?

Recurrence: Hₙ = 2H_{n−1} + 1 with H₁ = 1. Closed-form solution: Hₙ = 2ⁿ − 1 moves.

What are the four levels (Types 0, 1, 2, 3) of the Chomsky Hierarchy of formal grammars and their corresponding automata?

- Type 3: Regular Grammars ↔ Finite Automata (DFA/NFA) - Type 2: Context-Free Grammars ↔ Pushdown Automata (PDA) - Type 1: Context-Sensitive Grammars ↔ Linear Bounded Automata (LBA) - Type 0: Unrestricted Grammars ↔ Turing Machines.

State the Master Theorem for divide-and-conquer recurrences T(n) = a T(n/b) + Θ(n^d) (where a ≥ 1, b > 1, d ≥ 0).

Let c = log_b(a): 1. If d c: T(n) = Θ(n^d).

What is the chromatic number χ(G) of a graph, and what does the Four Color Theorem state?

χ(G) is the minimum number of colors needed to color the vertices of G so that no two adjacent vertices share the same color. The Four Color Theorem states that χ(G) ≤ 4 for every planar graph G.

Why are K₅ and K_{3,3} non-planar, and what does Kuratowski's Theorem state?

For K₅ (v = 5, e = 10), 3v − 6 = 9 < 10; for triangle-free K_{3,3} (v = 6, e = 9), 2v − 4 = 8 < 9. Kuratowski's Theorem states that a finite graph is planar if and only if it contains no subgraph homeomorphic to (a subdivision of) K₅ or K_{3,3}.

What are the necessary and sufficient conditions for an undirected multigraph (with at least one edge) to have an Eulerian circuit or an open Eulerian trail (path)?

Assuming all vertices of positive degree belong to a single connected component: - Eulerian circuit (closed trail visiting every edge exactly once): every vertex has even degree. - Open Eulerian trail (starts and ends at distinct vertices): exactly two vertices have odd degree.

State Euler's Formula for connected planar graphs and the resulting edge upper bounds.

For a connected planar drawing with v vertices, e edges, and f faces (regions), v − e + f = 2. For simple connected planar graphs with v ≥ 3, e ≤ 3v − 6 (and e ≤ 2v − 4 if the graph is triangle-free).

What are the four equivalent characterizations of an undirected tree T with n vertices?

1. T is connected and acyclic. 2. T is connected and has n − 1 edges. 3. T is acyclic and has n − 1 edges. 4. There is a unique simple path between every pair of vertices in T.

What are Stirling numbers of the second kind S(n, k) and Bell numbers Bₙ?

S(n, k) counts the number of ways to partition an n-element set into k non-empty unlabeled subsets (satisfying S(n, k) = k S(n−1, k) + S(n−1, k−1)). The Bell number Bₙ = Σ_{k=0}^n S(n, k) is the total number of partitions of an n-element set.

How is a Deterministic Finite Automaton (DFA) formally defined as a 5-tuple?

M = (Q, Σ, δ, q₀, F), where Q is a finite set of states, Σ is a finite input alphabet, δ: Q × Σ → Q is the transition function, q₀ ∈ Q is the start state, and F ⊆ Q is the set of accepting (final) states.

How do weak connectivity and strong connectivity differ in a directed graph (digraph)?

A digraph is strongly connected if there is a directed path from u to v and from v to u for every pair of vertices; it is weakly connected if replacing all directed edges with undirected edges produces a connected graph.

In a full m-ary tree, if every internal vertex has exactly m children and there are i internal vertices, how many total vertices n and leaves l does the tree have?

Total vertices: n = m·i + 1. Leaves: l = (m − 1)i + 1.

State Cayley's Formula for the number of labeled trees on n vertices.

There are n^{n−2} distinct labeled trees on n ≥ 2 vertices (established via Prüfer sequences of length n − 2).

State the Handshaking Lemma for an undirected graph G = (V, E) and its consequence for odd-degree vertices.

The sum of the degrees of all vertices equals twice the number of edges: Σ_{v ∈ V} deg(v) = 2|E|. Consequently, every undirected graph has an even number of vertices of odd degree.

What is the recurrence relation and Binet's closed-form formula for the Fibonacci numbers Fₙ?

F₀ = 0, F₁ = 1, and Fₙ = F_{n−1} + F_{n−2} for n ≥ 2. Binet's formula is Fₙ = (φⁿ − ψⁿ) / √5, where φ = (1 + √5)/2 and ψ = (1 − √5)/2.

What are the numbers of vertices and edges in the complete graph Kₙ, complete bipartite graph K_{m,n}, and n-dimensional hypercube Qₙ?

- Kₙ: n vertices, n(n − 1)/2 edges. - K_{m,n}: m + n vertices, m · n edges. - Qₙ: 2ⁿ vertices, n · 2^{n−1} edges.

Graph Theory, Trees, Recurrence Relations, Generating Functions & Automata

Mathematical and algorithmic foundations for AI and computer science: graph search and spanning trees, asymptotic recurrences, generating functions, combinatorial structures, Boolean logic normal forms (CNF/DNF), and formal automata.

Level: advanced
Languages: en → en
Cards: 32
Markdown: Graph Theory, Trees, Recurrence Relations, Generating Functions & Automata (.md)

Flashcards (32)

#	Front (Term / Question)	Back (Definition / Answer)
1	How is the Pumping Lemma for regular languages used to prove that L = {0ⁿ1ⁿ \| n ≥ 0} is not regular?	If L were regular with pumping length p, choose s = 0^p 1^p ∈ L. For any split s = xyz with \|xy\| ≤ p and \|y\| ≥ 1, y consists solely of 0s (y = 0^k, k ≥ 1). Pumping to xy²z = 0^{p+k}1^p yields unequal numbers of 0s and 1s, so xy²z ∉ L — a contradiction.
2	What is the Extended Binomial Series expansion for 1 / (1 − x)^k (k ≥ 1), and what is the coefficient of xⁿ?	1 / (1 − x)^k = Σ_{n=0}^∞ C(n + k − 1, n) xⁿ, so the coefficient [xⁿ] is C(n + k − 1, k − 1).
3	What is the Ordinary Generating Function (OGF) of a sequence {aₙ}, and what sequence corresponds to G(x) = 1 / (1 − cx)?	G(x) = Σ_{n=0}^∞ aₙ xⁿ. For G(x) = 1 / (1 − cx) = Σ_{n=0}^∞ cⁿ xⁿ, the sequence is aₙ = cⁿ.
4	What is a bipartite graph, and what is König's characterization of bipartite graphs in terms of cycles?	A graph whose vertex set V can be partitioned into two disjoint independent sets V₁ and V₂ such that every edge connects a vertex in V₁ to one in V₂. A graph is bipartite if and only if it contains no cycles of odd length.
5	What is the minimum height of a binary tree with l leaves, and why does this imply the Ω(n log n) lower bound for comparison-based sorting?	A binary tree of height h has at most 2^h leaves, so h ≥ ⌈log₂ l⌉. A comparison decision tree sorting n elements must have at least n! leaves, requiring worst-case height ≥ log₂(n!) = Θ(n log n).
6	State Kleene's Theorem connecting regular expressions and finite automata.	A formal language L ⊆ Σ* is regular (recognized by some DFA/NFA) if and only if it can be described by a regular expression built from ∅, ε, alphabet symbols, union (∪), concatenation (·), and Kleene star (*).
7	How is a second-order linear homogeneous recurrence relation aₙ = c₁ a_{n−1} + c₂ a_{n−2} solved using its characteristic equation?	Solve r² − c₁ r − c₂ = 0: - If roots r₁ ≠ r₂ are distinct: aₙ = α r₁ⁿ + β r₂ⁿ. - If there is a repeated root r₀: aₙ = (α + β n) r₀ⁿ.
8	What does the k-th power A^k of the adjacency matrix A of a graph G represent?	The entry (A^k)_{ij} equals the exact number of walks of length k from vertex vᵢ to vertex vⱼ in G.
9	How does a Hamiltonian cycle differ from an Eulerian circuit, and what do Dirac's and Ore's Theorems guarantee?	A Hamiltonian cycle visits every vertex exactly once (deciding existence is NP-complete, unlike Eulerian circuits). For a simple graph on n ≥ 3 vertices, Ore's Theorem guarantees a Hamiltonian cycle if deg(u) + deg(v) ≥ n for every non-adjacent pair u ≠ v, and Dirac's Theorem guarantees one if deg(v) ≥ n/2 for every vertex v.
10	What are the axioms of a Boolean Algebra (B, +, ·, ', 0, 1)?	With distinct elements 0 ≠ 1: Associative laws, Commutative laws, Identity laws (x + 0 = x, x · 1 = x), Distributive laws (x · (y + z) = (x · y) + (x · z) and x + (y · z) = (x + y) · (x + z)), and Complement laws (x + x' = 1, x · x' = 0).
11	How does a Nondeterministic Finite Automaton (NFA) differ from a DFA, and why do they recognize the exact same class of languages?	An NFA allows transition function δ: Q × (Σ ∪ {ε}) → P(Q) (multiple or zero next states and ε-transitions). By the Subset (Powerset) Construction, any k-state NFA can be converted into an equivalent DFA with at most 2^k states.
12	How do Kruskal's and Prim's greedy algorithms construct a Minimum Spanning Tree (MST)?	Kruskal's algorithm sorts all edges by weight and repeatedly adds the lightest edge that does not create a cycle (using Union-Find). Prim's algorithm grows a single connected tree from a starting vertex by repeatedly adding the cheapest edge crossing the cut.
13	What is the formula for the n-th Catalan number Cₙ, and what classic combinatorial structures does it count?	Cₙ = (1 / (n + 1)) C(2n, n). It counts balanced parentheses strings of length 2n, full binary trees with n + 1 leaves, Dyck paths from (0,0) to (2n,0), and triangulations of a convex (n + 2)-gon.
14	What is the difference between Disjunctive Normal Form (DNF) and Conjunctive Normal Form (CNF), and why is {NAND} functionally complete?	DNF is a disjunction (OR) of conjunctive terms (ANDs of literals; in full canonical DNF, a sum of minterms), whereas CNF is a conjunction (AND) of disjunctive clauses (ORs of literals; in full canonical CNF, a product of maxterms). {NAND} is functionally complete because NOT, AND, and OR can all be constructed using only NAND gates (e.g., ¬x = x NAND x).
15	State Hall's Marriage Theorem for bipartite graphs.	A bipartite graph G = (V₁, V₂, E) has a complete matching saturating every vertex of V₁ if and only if for every subset S ⊆ V₁, the neighborhood satisfies \|N(S)\| ≥ \|S\|.
16	What is graph isomorphism, and what are common graph invariants used to prove two graphs are NOT isomorphic?	Two graphs G₁ and G₂ are isomorphic if there is a bijection f: V(G₁) → V(G₂) preserving adjacency. Common invariants include vertex count, edge count, degree sequence, number of connected components, and lengths of simple cycles.
17	What is the recurrence relation and closed-form solution for the Tower of Hanoi puzzle with n disks?	Recurrence: Hₙ = 2H_{n−1} + 1 with H₁ = 1. Closed-form solution: Hₙ = 2ⁿ − 1 moves.
18	What are the four levels (Types 0, 1, 2, 3) of the Chomsky Hierarchy of formal grammars and their corresponding automata?	- Type 3: Regular Grammars ↔ Finite Automata (DFA/NFA) - Type 2: Context-Free Grammars ↔ Pushdown Automata (PDA) - Type 1: Context-Sensitive Grammars ↔ Linear Bounded Automata (LBA) - Type 0: Unrestricted Grammars ↔ Turing Machines.
19	State the Master Theorem for divide-and-conquer recurrences T(n) = a T(n/b) + Θ(n^d) (where a ≥ 1, b > 1, d ≥ 0).	Let c = log_b(a): 1. If d < c: T(n) = Θ(n^{log_b a}). 2. If d = c: T(n) = Θ(n^d log n). 3. If d > c: T(n) = Θ(n^d).
20	What is the chromatic number χ(G) of a graph, and what does the Four Color Theorem state?	χ(G) is the minimum number of colors needed to color the vertices of G so that no two adjacent vertices share the same color. The Four Color Theorem states that χ(G) ≤ 4 for every planar graph G.
21	Why are K₅ and K_{3,3} non-planar, and what does Kuratowski's Theorem state?	For K₅ (v = 5, e = 10), 3v − 6 = 9 < 10; for triangle-free K_{3,3} (v = 6, e = 9), 2v − 4 = 8 < 9. Kuratowski's Theorem states that a finite graph is planar if and only if it contains no subgraph homeomorphic to (a subdivision of) K₅ or K_{3,3}.
22	What are the necessary and sufficient conditions for an undirected multigraph (with at least one edge) to have an Eulerian circuit or an open Eulerian trail (path)?	Assuming all vertices of positive degree belong to a single connected component: - Eulerian circuit (closed trail visiting every edge exactly once): every vertex has even degree. - Open Eulerian trail (starts and ends at distinct vertices): exactly two vertices have odd degree.
23	State Euler's Formula for connected planar graphs and the resulting edge upper bounds.	For a connected planar drawing with v vertices, e edges, and f faces (regions), v − e + f = 2. For simple connected planar graphs with v ≥ 3, e ≤ 3v − 6 (and e ≤ 2v − 4 if the graph is triangle-free).
24	What are the four equivalent characterizations of an undirected tree T with n vertices?	1. T is connected and acyclic. 2. T is connected and has n − 1 edges. 3. T is acyclic and has n − 1 edges. 4. There is a unique simple path between every pair of vertices in T.
25	What are Stirling numbers of the second kind S(n, k) and Bell numbers Bₙ?	S(n, k) counts the number of ways to partition an n-element set into k non-empty unlabeled subsets (satisfying S(n, k) = k S(n−1, k) + S(n−1, k−1)). The Bell number Bₙ = Σ_{k=0}^n S(n, k) is the total number of partitions of an n-element set.
26	How is a Deterministic Finite Automaton (DFA) formally defined as a 5-tuple?	M = (Q, Σ, δ, q₀, F), where Q is a finite set of states, Σ is a finite input alphabet, δ: Q × Σ → Q is the transition function, q₀ ∈ Q is the start state, and F ⊆ Q is the set of accepting (final) states.
27	How do weak connectivity and strong connectivity differ in a directed graph (digraph)?	A digraph is strongly connected if there is a directed path from u to v and from v to u for every pair of vertices; it is weakly connected if replacing all directed edges with undirected edges produces a connected graph.
28	In a full m-ary tree, if every internal vertex has exactly m children and there are i internal vertices, how many total vertices n and leaves l does the tree have?	Total vertices: n = m·i + 1. Leaves: l = (m − 1)i + 1.
29	State Cayley's Formula for the number of labeled trees on n vertices.	There are n^{n−2} distinct labeled trees on n ≥ 2 vertices (established via Prüfer sequences of length n − 2).
30	State the Handshaking Lemma for an undirected graph G = (V, E) and its consequence for odd-degree vertices.	The sum of the degrees of all vertices equals twice the number of edges: Σ_{v ∈ V} deg(v) = 2\|E\|. Consequently, every undirected graph has an even number of vertices of odd degree.
31	What is the recurrence relation and Binet's closed-form formula for the Fibonacci numbers Fₙ?	F₀ = 0, F₁ = 1, and Fₙ = F_{n−1} + F_{n−2} for n ≥ 2. Binet's formula is Fₙ = (φⁿ − ψⁿ) / √5, where φ = (1 + √5)/2 and ψ = (1 − √5)/2.
32	What are the numbers of vertices and edges in the complete graph Kₙ, complete bipartite graph K_{m,n}, and n-dimensional hypercube Qₙ?	- Kₙ: n vertices, n(n − 1)/2 edges. - K_{m,n}: m + n vertices, m · n edges. - Qₙ: 2ⁿ vertices, n · 2^{n−1} edges.