Every problem from every sheet mapped to the resource that teaches it — grouped where one source covers a whole block.
| # | Problem | Specific resource |
|---|---|---|
| P1–P9 | Word lengths, alphabet identification, counting words, Kleene star, prefixes/suffixes/subwords, words of length 5 in L* | 🎥 Neso — FL playlist covers all |
| P10 | L₁={ba^k:k≤2}, L₂={|x|=1}: compute 10 language operations (union, intersection, concatenation, complement, palindromes…) | 📘 Udemy 1 — S2 Language Theory🎥 Neso — Language Operations |
| P11 | Properties of addition, concatenation, multiplication (internal, associative, commutative?) | 🎥 Neso — FL playlist |
| P12–P13 | L₁={|A|=2}, L₂={|A|=5}: describe Kleene-closure operations. Words of length 10 in MULTIPLICATION and ADDITION. | 📘 Udemy 1 — S2 Language Theory |
| # | Problem | Specific resource |
|---|---|---|
| P1–P3 | MULTIPLICATION ∩ OPALINDROMES; complement/set operations on L₁, L₂; words in Σ* \ (Σ₁* ∪ Σ₂*) | 🎥 Neso — FL playlist |
| P4–P6 | Language operations on specific L₁, L₂ (union, concat, Kleene star, complement, palindromes, powers) | 📘 Udemy 1 — S2🎥 Neso — FL playlist |
| P7–P10 | Relations between L₁* and L₂*; counterexamples; relations between L₁*+L₂* vs (L₁+L₂)*, L₁*·L₂* vs (L₁·L₂)*, etc. | 🎥 Neso — Kleene closure properties |
| P11 | Which distributivity identities hold for any L₁, L₂, L₃? | 🎥 Neso — FL playlist |
| P12 | Prove: (L⁺)* = (L*)*, (L⁺)⁺ = L⁺, (L*)⁺ = (L⁺)*\Λ | 📘 Udemy 1 — S2🎥 Neso — Closure identity proofs |
| # | Problem | Specific resource |
|---|---|---|
| P1–P4 | List words in given regex languages; membership tests (does word belong to L?) | 🎥 Neso — Regex intro & membership |
| P5–P8 | Simplify regex expressions; equivalence of regex; shortest word not in L; which language description matches a regex | 📗 Udemy 2 — S4 Regex🎥 Neso — Regex simplification |
| P9 | Describe 10 languages generated by given regex (reading/interpreting regex) | 🎥 Neso — Reading regex📘 Udemy 1 — S3 |
| P10 | Write regex for 15 word-property languages (|A|<4, divisibility of length, a-count divisible by 3, subword patterns…) | 📘 Udemy 1 — S3 Language Problems📗 Udemy 2 — S4🎥 Neso — Regex construction |
| P11–P12 | Dependencies between L(A), L(A+Λ), L(A·A) etc.; find A, B where L(AA)≠L(A), L(AB)≠L(BA) | 🎥 Neso — Regex laws |
| P13–P14 | Prove 4 pairs generate same language; check equivalence of 9 regex pairs | 📗 Udemy 2 — S4 Regex equivalence🎥 Neso — Proving regex equality |
| # | Problem | Specific resource |
|---|---|---|
| P1 | DFA with 4 states: identify type, trace δ̂(s₀, A) for 4 words, determine acceptance | 📗 Udemy 2 — S1: DFA tracing🎥 Neso — DFA tracing |
| P2 | NFA with set-valued δ: identify type, trace δ̂(s₀, A), determine acceptance | 📗 Udemy 2 — S1: NFA🎥 Neso — NFA tracing |
| P3 | NFA-Λ with epsilon transitions: identify type, trace using ε-closure, determine acceptance | 📗 Udemy 2 — S2: NFA-ε🎥 Neso — ε-NFA & ε-closure |
| P4 (a–n) | 14 automaton diagrams: describe accepted language + write corresponding regex for each | 📘 Udemy 1 — S4 FA Problems🎥 Neso — Language from FA🛠 JFLAP — draw & test |
| P5 (a–q) | Construct DFA + regex for 17 word-property languages over {a,b} | 📘 Udemy 1 — S5 FA Problems📗 Udemy 2 — S1 DFA construction🎥 Neso — DFA construction🛠 JFLAP — build & verify |
| P6 (a–e) | 5 pairs of automata: determine all possible language relations (=, ⊂, ⊃, disjoint, overlapping) | 📗 Udemy 2 — S6 FA Equivalence |
| P7 (a–f) | 6 NFA-Λ diagrams: convert each to an equivalent DFA (subset construction + ε-closure) | 📗 Udemy 2 — S1 NFA→DFA🎥 Neso — Subset construction🛠 JFLAP — auto-convert NFA→DFA |
| # | Problem | Specific resource |
|---|---|---|
| P1 (a–d) | Build DFA for 4 given regex languages, then check if the result is already minimal | 📗 Udemy 2 — S6🎥 Neso — DFA Minimization |
| P2 (a–f) | 6 given automaton diagrams: produce the minimal DFA for each using table-filling algorithm | 📗 Udemy 2 — S6🎥 Neso — Table-filling algorithm🛠 JFLAP — verify minimization |
| # | Problem | Specific resource |
|---|---|---|
| P1 (a–h) | Build NFA for 8 regex languages using Thompson's construction (Kleene proof method): ab*, a+b*, ab*+a, a*ba*+b*, and more complex compositions | 📗 Udemy 2 — S4: Regex→NFA🎥 Neso — Thompson construction🛠 JFLAP — regex→NFA converter |
| P2 (a–g) | 7 automaton diagrams: extract regular expression from each using state-elimination (Arden's lemma / Kleene reverse direction) | 📗 Udemy 2 — S4: NFA→Regex🎥 Neso — NFA to Regex🛠 JFLAP — FA→regex converter |
| # | Problem | Specific resource |
|---|---|---|
| P1 | Explain why every finite language is regular | 📗 Udemy 2 — S5 |
| P2 | Prove: if L₁, L₂ regular then L₁\L₂ is regular; L₁△L₂ is regular | 📗 Udemy 2 — S5: Closure Properties🎥 Neso — Closure of Regular Languages |
| P3 | Prove: if L₁ irregular and L₂, L₁∩L₂ are regular, then L₁∪L₂ is irregular | 📗 Udemy 2 — S5🎥 Neso — Indirect proofs |
| P4 (a–h) | Pumping lemma: show 8 languages are not regular — a²ⁿbⁿ, aⁿbⁿaⁿ, aⁿbaⁿ, primes, AA, MULTIPLICATION, aⁿbᵐcᵏ (n+m=k), a²ⁿ⁺¹b⁴ⁿ⁺³ | 📗 Udemy 2 — S5🎥 Neso — Pumping Lemma examples |
| P5 (a–c) | Prove over Σ={a}: a^(2ⁿ), a^(n²), a^(n!) are not regular (exponential/quadratic/factorial growth) | 📗 Udemy 2 — S5🎥 Neso — Pumping Lemma advanced |
| P6 (a–c) | Find irregular L₁, L₂ over {a} such that L₁+L₂, L₁∩L₂, L₁\L₂ is each regular (counterexamples) | 📗 Udemy 2 — S5: Closure Properties |
| # | Problem | Specific resource |
|---|---|---|
| P1 (a–c) | Find regular grammars generating 3 regular languages: L((aaa+b)*), odd-length words, exactly-one-a-or-b words | 📗 Udemy 2 — S7: Regular Grammars & FA🎥 Neso — Regular Grammar construction |
| P2 (a–c) | 3 given regular grammars: find equivalent regular expressions using Arden's lemma / state-elimination on grammar→FA | 📗 Udemy 2 — S7: Grammar→Regex🎥 Neso — Regular Grammar to Regex🛠 JFLAP — Grammar→FA→Regex |
| P3 (a–q) | Describe languages of 17 CFGs (including S→aS|Λ, palindrome-like, counting, nested structures…) | 📘 Udemy 1 — S6 CFG Problems📗 Udemy 2 — S8: CFGs🎥 Neso — Describing CFG languages |
| P4 | Which of P3's languages are also regular? Write regular grammars for those. | 📗 Udemy 2 — S7🎥 Neso — Regular vs CF |
| P5 (a–w) | Find CF or regular grammars for 23 languages over {a,b}: length constraints, pattern constraints, counting (aⁿbᵐ with inequalities), equal counts, palindromes… | 📘 Udemy 1 — S6–S7📗 Udemy 2 — S8 CFG construction🎥 Neso — CFG construction examples |
| P6 (a–d) | Construct derivation trees + write leftmost/rightmost derivations for specific words in 4 given grammars | 📗 Udemy 2 — S8: Derivation Trees🎥 Neso — Parse Trees & Derivations🛠 JFLAP — derivation visualizer |
| P7 (a–d) | Show 4 grammars are ambiguous — find 2 distinct parse trees for one word in each | 📗 Udemy 2 — S8: Ambiguous Grammars🎥 Neso — Ambiguous Grammars |
| P8 (a–b) | For 2 given CF grammars that happen to be regular, find equivalent regular grammars | 📗 Udemy 2 — S7: Regular Grammars & FA🎥 Neso — CF→Regular (when possible)🛠 JFLAP — Grammar→FA→Grammar |