2. Множество L не содержит последовательностей, имеющих два одинаковых символа подряд

Если через обозначить множество входных последовательностей длины , через Е — множество, содержащее все возможные входные последовательности, то, очевидно, будет выполняться соотношение

Если число групп эквивалентных состояний обозначить через , число групп состояний, эквивалентных относительно L — через , а число групп состояний, эквивалентных относительно — через , то из (9.2) следует

В пункте 1 этого параграфа было показано, что в рассматриваемом случае разбиения на группы эквивалентных состояний и на группы состояний, эквивалентных относительно , совпадают.

Следовательно, , и из (9.2) получаем

Поэтому в рассматриваемом случае , эквивалентные относительно будут эквивалентны и относительно Е. Минимизацию можно провести, заменив каждую группу состояний одним состсюнием по способу, изложенному выше, когда считалось, что . Итак, в рассматриваемом случае минимальные П-машины для множества Е и для множества L совпадают, и минимизацию можно проводить так, как будто бы на входные последовательности никаких ограничений не наложено.