Как я могу построить конечные автоматы

Должен ли я включать 0 в качестве строки из этого набора?

да

И как мне это сделать?

Чтобы построить конечный автомат, вам нужно идентифицировать состояния и переходы. Теорема Майхилла-Нероде позволяет вам найти необходимые (и достаточные!) состояния для конечного автомата, если вы можете идентифицировать классы эквивалентности «неразличимых» строк.

Две строки x и y в этом смысле неразличимы, если для любой другой строки z либо обе строки xz, либо yz присутствуют в языке, либо ни одна из них.

В вашем случае попробуем определить классы эквивалентности. Пустая строка находится в некотором классе эквивалентности. Строка 0 находится в другом эквивалентном классе, так как вы можете добавить пустую строку к 0 и получить строку на языке (в то время как вы не можете добавить пустую строку к пустой строке, чтобы получить строку на языке). На данный момент мы нашли два разных класса эквивалентности — один для пустой строки, другой для 0. Для обоих из них потребуются разные состояния в нашей FA.

А как насчет строки 1? Его можно отличить как от 0, так и от пустой строки, поскольку вы можете добавить 10 к 1, чтобы получить 110, строку на языке, но вы не можете добавить его к 0 или пустой строке, чтобы получить строку на языке. Итак, у нас есть еще одно государство.

Как насчет строки 00? Эта строка не на языке, и никакая другая строка не может быть добавлена ​​к этой строке, чтобы получить строку на языке. Это еще один класс эквивалентности. Оказывается, следующие строки, 01 и 10, тоже относятся к этому классу.

Строка 11 оказывается в том же классе, что и пустая строка: вы можете добавить любую строку на языке к 11 и получить другую строку на языке. Если вы попробуете все строки длины 3, вы обнаружите, что все они уже попадают в один из вышеуказанных классов, и вы можете прекратить проверку на этом этапе.

Итак, у нас есть четыре состояния — назовем их [-], [0], [1] и [00]. Теперь разбираемся с переходами.

Если вы получите 0 в [-], вам нужно перейти к [0]... а если вы получите 1, вам нужно перейти к [1]. В остальном просто выясните, какую строку вы получите, добавив к канонической, и в каком классе будет полученная строка... и перейдите в это состояние.