Регулярное выражение, которое я получил, постепенно извлекая узлы (порядок: 3,1,2,0):
(aa|bb|(ab|ba)(bb|aa)*(ab|ba))*
Насколько я могу судить, это самое простое.(Я хотел бы знать, есть ли у кого-то более простое сокращение - я действительно проверяю этот материал на этой неделе!)
Пошаговый процесс
Мы начинаем сдобавление нового начала и принятия состояния.Каждое старое состояние принятия (в данном случае только одно) связывается с новым состоянием принятия с ε-переходом:
Далее мы копируемсостояние out 3. Нам нужно сохранить все пути, проходящие через состояние 3. В этом случае мы добавили путь из состояния 0 обратно в себя, пути из состояния 0 в состояние 2 и состояние 2 обратно в себя:
Мы делаем то же самое с состоянием 1:
Мы можем упроститьэто немного: мы будем объединять циклические переходы запятыми.(В конце концов, это превратится в оператор объединения (| или ⋃ и т. Д. В зависимости от вашей записи).
МыЗатем мы удалим состояние 2 и поместим все в один большой цикл:
Петли становятся звездами; мы удаляем последнее состояние, поэтому у нас просто естьпереход из начального состояния в конечное состояние, связанное с одним большим регулярным выражением:
И это наше регулярное выражение!
Определение языка
Вы довольно близки с определением языка. Если вы можете позволить что-то более слабое, это будет так:
L = { w | w contains an even number of 'a's and 'b's }
Проблема с вашим определением заключается в том, что вы начинаетестрока w выключается с a каждый раз, тогда как единственным ограничением является соотношение числа a и b.