Хороший способ подумать о ТВС - это попытаться подумать о том, в скольких различных ситуациях вы можете оказаться, с точки зрения того, как вы собираетесь получить строку в языке. Давайте начнем с нескольких небольших строк и посмотрим, что я имею в виду.
Скажем, вы начинаете с пустой строки. Что вы можете добавить к этому, чтобы получить строку на языке? Ну, пустая строка в языке, так что мы можем добавить пустую строку (то есть, ничего), а также иметь строку на языке. Кроме того, мы можем добавить любую строку на языке, к которому мы стремимся, к пустой строке, и мы получим строку на языке (тривиально). Нам понадобится хотя бы одно состояние, чтобы запомнить пустую строку (и подобные ей строки - строки, к которым мы можем добавить пустую строку или любую другую строку в языке и при этом иметь строку в языке); это будет начальное / начальное состояние, и поскольку пустая строка находится на языке (мы это легко проверяем), мы знаем, что начальное / начальное состояние будет приниматься.
Теперь давайте рассмотрим строку a. Это пример строки, отсутствующей в языке, и мы ничего не можем добавить в конец этой строки, чтобы она была в языке; мы уже нарушили условие, что все a в строке предшествуют b. Набор строк, который мы можем добавить к этому, чтобы получить строку в языке, является пустым набором, и поэтому нам понадобится состояние, отличное от того, которое мы уже определили, чтобы запомнить эту строку и строки, подобные ей - строки, к которым мы не можем ничего добавить, чтобы получить строку в языке.
Напомним, что мы определили два состояния: принимающее начальное / начальное состояние и то, что мы называем «мертвым» состоянием - состояние, которое не принимает и которое никогда не приводит к принимающему состоянию.
Давайте попробуем строку b. Эта строка на языке, и мы можем добавить к ней пустую строку. Мы также можем тривиально добавить любую другую строку в языке в конец этой строки и получить другую строку в языке. Тем не менее, мы также можем добавить a, за которым следует любая строка в языке, и получить другую строку в языке. Например, мы можем добавить строку a, за которой следует bbabb, чтобы получить babbabb, которая также есть в языке. Поэтому набор строк, который мы можем добавить, является набором, которого мы не видели раньше, и нам потребуется новое состояние для представления этой строки - строки b - и подобных строк. Он будет принимать, поскольку строка b является строкой в языке.
Вы должны попробовать строки aa, ab, ba и bb. Вы должны обнаружить, что строки aa и ab обе уже охвачены нашим мертвым состоянием (мы не можем добавить строки в их конец, чтобы получить что-либо на нашем языке), и что строка ba покрыта start / initial состояние (мы можем только добавить к этой строке уже в языке, чтобы получить другие строки в языке), и что bb соответствует третьему состоянию, которое мы определили (добавление любой строки или единственного а, за которым следует любая строка, приведет к Строка также на языке). Поскольку мы исчерпали все строки длины 2 и не добавили никаких новых состояний, мы знаем, что это все состояния, которые нам нужны в FA; мы могли бы добавить других, но они были бы излишними.
Чтобы получить переходы, все, что нам нужно сделать, - это убедиться, что все состояния ведут в правильное место.Другими словами, поскольку строка a формируется путем добавления символа a в конец пустой строки, нам необходим переход из начального / начального состояния (соответствующего пустой строке) в мертвое состояние (соответствующее строке a), который происходит, когда FA читает символ a.Точно так же нам нужен переход из начального / начального состояния в третье состояние на символе b.Другие переходы обнаруживаются аналогичным образом: либо на a, либо на ab мертвое состояние переходит в себя, а третье состояние возвращается в цикл на b и переходит в начальное / начальное состояние на a.Как только каждое состояние имеет переход для каждого символа в алфавите, у вас есть полный (и правильный) FA.Более того, создавая его таким образом, вы гарантируете, что у вас есть минимальный FA ... который является хорошим способом решения проблем, запрашивающих один, вместо того, чтобы придумать произвольный и минимизировать его пост-hoc.