Practice Problems:
The following is a list 100 challenging practice problems. These problems are not graded, but regular submission helps you stay engaged with the material and reinforce the core concepts. You are welcome to discuss them with classmates or the teaching staff and use any resources or tools you find helpful. Their purpose is to support your learning, not evaluate it.
| Date | Problem |
|---|---|
| Jan 19 | Let n ∈ ℕ. Consider the alphabet {a, b} and define the language Ln to consist of all words in which the difference between the number of occurrences of a and the number of occurrences of b is divisible by n. Show that for all n, Ln is regular. |
| Jan 20 | Consider a first-order logic specification of a formal language over the alphabet {a, b, c}, with positions in a word as the domain of discourse and unary predicates A(x), B(x), and C(x) indicating that position x contains the symbols a, b, and c, respectively. Let S(x, y) denote that y is the successor of x. Show that the language expressed by the formula: ∀x ( A(x) → ∃y ( S(x, y) ∧ B(y) ) ) is regular. Is every language definable by such a first-order formula regular? Can every regular language over {a, b, c} be expressed using such an FOL formula? |
| Jan 21 | Prove that a DFA accepts an infinite language if and only if its transition graph contains a directed cycle that is both reachable from the initial state and co-reachable (i.e., some accepting state is reachable from it). |
| Jan 22 | Construct, for every n ∈ ℕ, a regular language Ln such that Ln has an NFA with at most n states, and every equivalent DFA requires at least 2n states. Give a specific language and prove both the upper and lower bounds. |
| Jan 23 | Show that every NFA with multiple accepting states can be transformed into an equivalent NFA with exactly one accepting state. Show that every NFA with multiple initial states can be transformed into an equivalent NFA with exactly one initial state. |
| Jan 24 | Given a regular language L as a DFA, construct a DFA for the reverse of the language. Show that there is a family of languages Ln with DFA of size O(n) such that any DFA for the reversed language reverse(Ln) has size ≥2n. |
| Jan 25 | For each n≥1, construct regular languages An and Bn over the alphabet {a,b}such that the DFA for An and Bn are of size O(n) and any DFA for the concatenation language AnBn has size ≥2n. |
| Jan 26 | Prove that the language of a unary NFA is a finite union of arithmetic progressions (i.e., ultimately periodic). |
| Jan 27 | A synchronizing word is a an input to the DFA that sends any state of the DFA to one and the same state. That is, w ∈ Σ* such that there exists a state q*, for all states q, δ(q, w) = q*. Design an algorithm to determine if a given DFA has a synchronizing word. Hint: Use subset construction for a naive algorithm. |
| Jan 28 | Consider Ln from Jan 19. Show that the intersection of all Lp, taken over every prime number p, is exactly the set of all words in which the number of occurrences of a is equal to the number of occurrences of b. |
| Jan 29 | Prove the pumping lemma: Let L be a regular language. Then there exists a constant p ( such that every word w in L with length at least p can be written as w = xyz, where |xy| ≤ p, |y| ≥ 1, and for all k ≥ 0, the word xykz is also in L. |
| Jan 30 | Let p(n) be a polynomial with integer coefficients such that p(n) ≥ 0 for all n ∈ ℕ. Consider the unary language Lp = { ap(n) : n ∈ ℕ }. Prove that Lp is regular if and only if the polynomial p is at most linear. |
| Jan 31 | Over the alphabet {a,b,c}, define L = { a bn cn : n ≥ 0 } ∪ { ak w : k ≥ 2 and w ∈ {a,b,c}*}. Show that L is not regular and yet it satisfies the pumping lemma (Jan 29 problem). |
| Feb 1 | Over the alphabet {a, b}, consider the set of all words in which the number of occurrences of a is equal to the number of occurrences of b. Show that this language is not regular. Using the answers of problems from Jan 19, Jan 28, and Feb 1, arrive at a contradiction to the claim that there are finitely many prime numbers. |
| Feb 2 | Let Σ be a finite alphabet and let L ⊆ Σ* be a language (not necessarily regular). Let M be the set of equivalence classes induced by the Myhill-Nerode relation (for w ∈ Σ*, let [w] denote its equivalence class). Define a binary operation on M by: [x] ⋅ [y] = [xy]. Prove that (M, ⋅, [ε]) is a well defined monoid. |
| Feb 3 | A language L is recognised by a monoid M if there exists a monoid homomorphism φ:Σ* → M and a subset F⊆M such that L=φ^(-1)(F). Equivalently, L consists exactly of those words whose image under φ lies in F. Prove that a language is regular if and only if it is recognised by a finite monoid. |
| Feb 4 | Let L be a language (not necessarily regular). Define L* to be the set of all finite concatenations of zero or more strings from L, that is L* = {wk : k ∈ ℕ }. Show that if L is a regular language, then L* is also a regular language. Show that the converse is not true. |
| Feb 5 | Fix a finite alphabet with a total order and the induced lexicographic order on words (≤). For a language L, its lexicographic downward closure ↓L = { w : ∃u ∈ L with w ≤ u }. Show that ↓L is regular when L is regular. |
| Feb 6 | Given regular expressions r, s, give a direct inductive proof that L(r) ∩ L(s) is regular without invoking automata. |
| Feb 7 | Given k ∈ ℕ (k > 0), consider the strings representing the binary encoding of numbers divisible by k. Show that any deterministic finite automaton recognizing this language must have at least k states. |
| Feb 8 | Let p be a polynomial with natural number coefficients and degree at least two. Consider the language consisting of all strings whose length is equal to p(n) for some natural number n. Use the Myhill–Nerode theorem to show that this language is not regular. |
| Feb 9 | Construct a weighted automaton over the real numbers with a single symbol alphabet {a} that generates a geometric distribution over strings. The automaton should assign weight (1 − α) α^k to the string a^k (for a parameter α). Now consider a generalisation, denoted D(α, m, c). This distribution assigns weight (1 − α) α^k to strings of the form a^(mk + c), and assigns weight 0 to all other strings (that is, strings whose length is not congruent to c modulo m). Show that this generalised distribution can also be represented by a weighted automaton. |
| Feb 10 | Create a weighted automaton over the real numbers with a single symbol alphabet {a} that maps a^n to n. Show that no deterministic weighted automata (that is an automata where every state has at most one outgoing transition labelled a, or where every word has a unique run) over reals can express this function. |
| Feb 11 | Consider languages R, S, and T (not necessarily regular). Show that (i) {ε}+R·R* = R*, (ii) R·R* = R·R*, and (iii) if X=(R·X) ∪ S then X=R*·S. If Y = (R·Y) ∪ (S·Y) ∪ T, what does it imply about Y? |
| Feb 12 | Let L be a language (not necessarily regular) over a singleton alphabet Σ = {a}. Show that L* is regular. |
| Feb 13 | If r is a regular expression, Consider a new operation r to denote its complement. That is L(r) = Σ* \ L(r). Regular expressions with only concatenation, union, and complement correspond to star-free languages (Feb 8 problem). Provide a star-free regular expression for the following languages: (i) { w in Σ* | w contains at least one a }, (ii) (ab)* (all repitions of ab), and (iii) {w∈Σ* | between the first and last a (if they exist) there is no b}. |
| Feb 14 | Consider a system of linear equations over finite languages, that is, a system of equations of the form Xi = Σj (cij * Xj) + di, where each cij and each di is a finite language. Show that if this system has a solution then this solution is unique, and every component language of the solution is regular. |
| Feb 15 | Prove that no weighted automata over real numbers with a singleton alphabet {a} can express the function f(an) = λn * e-λ / n! (the Poisson distribution with parameter λ). |
| Feb 16 | Similar to a push-down automaton with a stack, consider a finite-state automaton with a queue. Show that any langauge accepted by a push-down automaton with a stack is also accepted by a finite-state automaton with a queue. |
| Feb 17 | Show that any language accepted by a finite-state automaton with an array is regular. Note that the array length is a fixed constant independent of the input length. |
| Feb 18 | Show that L = { ww | w ∈ Σ* } can be accepted by a non-deterministic finite-state automaton with a queue (Feb 16 problem), but not a push-down automaton with a stack. |
| Feb 19 | A context-free grammar is linear if each production contains at most one non-terminal. Show that the language of well-balanced parentheses cannot be generated by a linear grammar. |
| Feb 20 | This problem extends the problem for Feb 14. Consider a system of polynomial equations over finite languages. Show that if this system has a solution then this solution is unique, and every component language of the solution is context-free language. |
| Feb 21 | Prove that the set of context-free languages is closed under union, concatenation, and Kleene star. |
| Feb 22 | Prove that the intersection of a regular language and a context-free language is context-free. The intersection of two context-free languages is not context-free. Using the result of Feb 21 problem, show that the set of context-free languages is not closed under complementation. |
| Feb 23 | A deterministic Turing machine has a single infinite tape and a read/write head. Prove that a finite-state automaton with two stacks can simulate a deterministic Turing machine. |
| Feb 24 | A k-counter machine is like a finite automaton equipped with k integer counters. Each counter can be incremented, decremented, and tested for zero. Show that a push-down automaton (with a stack) can simulate a 1-counter machine, but not vice-versa. |
| Feb 25 | Show that a deterministic k-tape Turing machine (TM) that runs in time T(n) on inputs of length n can be simulated by a single-tape Turing machine in time O(T(n)2). |
| Feb 26 | A Random Access Machine consists of a finite state machine (control unit), a finite number of registers for temporary storage, and an unbounded sequence of memory cells that can store integers. Unlike a Turing machine, which accesses memory sequentially along a tape, a RAM can directly access any memory cell in a single step, hence the term "random access." The machine operates by executing a sequence of instructions, which include arithmetic operations (such as addition, subtraction, and multiplication), data transfer between registers and memory cells, and conditional branching based on the contents of registers. Show that RAM is computationally equivalent to a deterministic Turing machine. |
| Feb 27 | Consider the language {anbncn∣n≥1}. Show that this language can be simulated by a 2-counter machine but not a 1-counter machine (and hence not a push-down automaton). |
| Feb 28 | An unrestricted grammar is a grammar in which each production rule has the form α → β, where α is a non-empty string of terminals and/or non-terminals, and β is any string of terminals and/or non-terminals (possibly empty). Show that every the class of languages generated by unrestricted grammars is equivalent to the class of languages accepted by a nondeterministic Turing machine. |
| Mar 1 | |
| Mar 2 | |
| Mar 3 | |
| Mar 4 | |
| Mar 5 | |
| Mar 6 | |
| Mar 7 | |
| Mar 8 | |
| Mar 9 | |
| Mar 10 | |
| Mar 11 | |
| Mar 12 | |
| Mar 13 | |
| Mar 14 | |
| Mar 15 | |
| Mar 16 | |
| Mar 17 | |
| Mar 18 | |
| Mar 19 | |
| Mar 20 | |
| Mar 21 | |
| Mar 22 | |
| Mar 23 | |
| Mar 24 | |
| Mar 25 | |
| Mar 26 | |
| Mar 27 | |
| Mar 28 | |
| Mar 29 | |
| Mar 30 | |
| Mar 31 | |
| Apr 1 | |
| Apr 2 | |
| Apr 3 | |
| Apr 4 | |
| Apr 5 | |
| Apr 6 | |
| Apr 7 | |
| Apr 8 | |
| Apr 9 | |
| Apr 10 | |
| Apr 11 | |
| Apr 12 | |
| Apr 13 | |
| Apr 14 | |
| Apr 15 | |
| Apr 16 | |
| Apr 17 | |
| Apr 18 | |
| Apr 19 | |
| Apr 20 | |
| Apr 21 | |
| Apr 22 | |
| Apr 23 | |
| Apr 24 | |
| Apr 25 | |
| Apr 26 | |
| Apr 27 | |
| Apr 28 |