patternMinor
Minimize Deterministic Finite Automata with no accepting states
Viewed 0 times
minimizefinitewithstatesautomataacceptingdeterministic
Problem
I have a finite automaton with no final/accepting states, so F is empty.
How do I minimize it?
I got this on a test and I didn't know how to approach the problem because the automaton had no accepting states.
Is a single initial state with all the transitions into itself the correct answer?
How do I minimize it?
I got this on a test and I didn't know how to approach the problem because the automaton had no accepting states.
Is a single initial state with all the transitions into itself the correct answer?
Solution
A finite automaton without end states denotes the language L = $ \emptyset $ . To minimize a DFA we minimize the number of states and the denoted language must be the same. By definition of DFA we must have an initial state $ q_0$ so $| Q | \geq 1$ and as you say we need to include the transition function with all transition into $ q_0 $ (because creating dead states is counterproductive).
Context
StackExchange Computer Science Q#42025, answer score: 7
Revisions (0)
No revisions yet.