Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 3 / 12F / a

Table of contents
- i a
  - Solution i
- ii a
  - Solution ii
- iii a
  - Solution iii
- iv a
  - Solution iv

i

Solution

A state

q

is inaccessible if no word reaches it from the initial state:

δ (q_{0}, w) \neq = q for every w \in W .

ii

Solution

States

q

and

q^{'}

are indistinguishable if no continuation can distinguish acceptance from them, that is, for every

w \in W

,

δ (q, w) \in F ⟺ δ (q^{'}, w) \in F .

iii

Solution

The automaton is irreducible if every state is accessible and no two distinct states are indistinguishable.

iv

Solution

An automaton accepting a regular language is irreducible exactly when it has the smallest possible number of states among deterministic automata accepting that language. The irreducible automaton is unique up to isomorphism; its states correspond to the Myhill--Nerode equivalence classes.

 Ancestors (10)

 View article source

 Discussion (0)

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