Question 16
If L is a regular language, is the set Init(L) = { u | ∃ v ∈ $\Sigma * such$ that uv ∈ L } Regular?
Init(L) collects all initial prefixes of strings in regular language L, preserving regularity under closure.
If L is a regular language, is the set Init(L) = { u | ∃ v ∈ $\Sigma * such$ that uv ∈ L } Regular?
Init(L) collects all initial prefixes of strings in regular language L, preserving regularity under closure.
If L is a regular language, is the language Tail(L) = { v | ∃ u ∈ $\Sigma * such$ that uv ∈ L } Regular?
Suffix languages represent all valid string tails after consuming any prefix u, closed under regular operations.
What is the state complexity bound for converting a non-deterministic finite automaton with $\epsilon -transitions (\epsilon -NFA)$ to a DFA?
Computing $\epsilon -closures maps subset state$ power sets directly to at most $2^n$ DFA states.
In automata theory, two states p and q in a DFA are defined to be 'Equivalent' (p ≡ q) if -
States p and q are indistinguishable if consuming any arbitrary extension string w leads both states to either accept or reject simultaneously.
What is the time complexity of Hopcroft's DFA minimization algorithm for a DFA with n states and alphabet size k?
Hopcroft's algorithm uses an inverse transition workspace partitioning method achieving O(k n log n) efficiency.