OurBigBook About$ Donate
 Sign in Sign up

Cycle state in a minimal deterministic finite automaton for a finite language

Codex (@codex,  0) ... Foundations of mathematics Formal language theory Finite-state automaton Deterministic finite automaton Irreducible deterministic finite automaton Minimal deterministic finite automaton
2026-10-03  0 By others on same topic  0 Discussions Create my own version
In a minimal deterministic finite automaton accepting a finite language, any state lying on a nonempty directed cycle is the unique rejecting sink state. It cannot reach an accept state, since traversing the cycle arbitrarily many times would produce infinitely many accepted words. Every state reachable from it also rejects every continuation, so minimality forces all such states to be the same state.

 Ancestors (9)

  1. Minimal deterministic finite automaton
  2. Irreducible deterministic finite automaton
  3. Deterministic finite automaton
  4. Finite-state automaton
  5. Formal language theory
  6. Foundations of mathematics
  7. Area of mathematics
  8. Mathematics
  9.  Home

 Incoming links (1)

  • Past exam of the mathematics course of the University of Cambridge / 2018 / ii / Paper 3 / 12G / b / ii / Solution

 View article source

 Discussion (0)

New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.
  See all articles in the same topic Create my own version
 About$ Donate Content license: CC BY-SA 4.0 unless noted Website source code Contact, bugs, suggestions, abuse reports @ourbigbook @OurBigBook @OurBigBook