BrainTok
ENESIT

Theory of Computation: Finite automata and regular languages · Deterministic Finite Automata

How deterministic finite automata work, what their finite memory can and cannot track, and how to design small ones.

Theory of Computation · 28 questions

Try 3 questions

1. For each state and input symbol, how many transitions does a deterministic finite automaton (DFA) define?

  1. At most one
  2. At least one
  3. Exactly one
Show the answer

Answer: Exactly one

Determinism means the transition function maps every (state, symbol) pair to exactly one next state, so the path through the machine on any input is completely fixed.

2. A DFA passes through an accepting state partway through a string but ends in a non-accepting state. Is the string accepted?

  1. Yes, reaching acceptance once is enough
  2. No, only the final state counts
  3. Only if the string is nonempty
Show the answer

Answer: No, only the final state counts

Acceptance is decided solely by the state the DFA is in after reading the last symbol; states visited along the way do not matter.

3. Besides knowing which state it is in, what memory does a DFA have?

  1. A read-write tape
  2. None at all
  3. A single counter
Show the answer

Answer: None at all

A finite automaton's only memory is which of its finitely many states it occupies, which is exactly why it cannot count without bound.

The rest of the quiz, a few questions at a time

BrainTok asks a few questions from quizzes like these before the apps you choose open, so your screen time turns into learning. For iPhone.

Join the beta

More Computer Science quizzes