Past exam of the mathematics course of the University of Cambridge / 2019 / ii / Paper 4 / 4H / a / iii

Table of contents
- Solution iii

Solution

Use the bounded-run deterministic finite automaton with states

q_{0}, q_{1}, \dots, q_{7}, q_{dead} .

State

q_{j}

records that the current suffix consists of exactly

j

consecutive zeros. Every

q_{0}, \dots, q_{7}

is accepting;

q_{dead}

is rejecting. Reading

1

sends every accepting state to

q_{0}

, while reading

0

sends

q_{j}

to

q_{j + 1}

for

j < 7

and sends

q_{7}

to

q_{dead}

. The dead state loops on both symbols. This finite automaton accepts exactly the words with no run of eight zeros, so

the language is regular .

 Ancestors (11)

 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