Возьмём за ос­но­ву пред­ло­жен­ный в на­чаль­ном ре­ше­нии ав­то­мат. Когда он за­кан­чи­ва­ет ра­бо­ту в со­сто­я­нии S0 это зна­чит, что стро­ка рас­по­зна­лась, а когда в S1  — что не рас­по­зна­лась. Нам же сей­час нужно сде­лать всё на­о­бо­рот, по­это­му S0 пе­ре­стаёт быть ко­неч­ным со­сто­я­ни­ем, зато им ста­но­вит­ся S1.

Кроме того, ис­ход­ный ав­то­мат во­об­ще не об­ра­ба­ты­вал слова, к ко­то­рых буквы а и b не че­ре­до­ва­лись. Те­перь нам нужны эти слова, по­это­му надо до­ба­вить их об­ра­бот­ку. Как толь­ко мы в со­сто­я­нии S0 встре­ча­ем букву b или в со­сто­я­нии S1 букву а, это сразу озна­ча­ет, что нам встре­ти­лось нуж­ное слово вне за­ви­си­мо­сти от того, что будет даль­ше. По­это­му в этом слу­чае мы пе­ре­хо­дим в ко­неч­ное со­сто­я­ние S2, ко­то­рое уже не по­ки­да­ем.

Ответ: см. рис.