HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Minimize Deterministic Finite Automata with no accepting states

Submitted by: @import:stackexchange-cs··
0
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?

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.