Search code examples
theoryfinite-automata

theory of computation: how can A be the language recognized by machine M1

This is taken from a theory of computation book:

If the diagram below represents machine M1,

enter image description here

how can A, the language machine M1 recognizes, be described as:

A = {w| w contains at least one 1 and an even number of 0s follow the last 1}

when the string 011 is accepted by machine M1. 011 in fact contains at least one 1, but an even number of 0s do not follow the last 1.

Then, isn't it incorrect to say "and even number of 0s follow the last 1"?

Solution

  • The set of natural numbers contains many even numbers. Working down from very large evens, we finally arrive at: ..., 6, 4, 2, 0. There are in fact zero 0s after the last 1, which is in that set.