Регулярное выражение для DFA

Нет, по нескольким причинам:

1. Ваш автомат bab
2. Ваш автомат не принимает ab
3. Ваш автомат не является DFA, по крайней мере, по некоторым строгим определениям

По первому пункту: начиная с q1 видим b, переходим к q2, видим a, переходим к q3, видим b и идем к q4, что принимает. Мы увидели bab и приняли его.

Что касается второго пункта: начиная с q1, мы видим a, но не имеем определенного перехода. Автомат «вылетает» и не принимает. Таким образом, никакая строка, начинающаяся с a, включая ab, не принимается.

Что касается третьего пункта: от DFA часто требуется показывать все состояния и переходы, включая мертвые состояния и переходы, которые никогда не вернутся в какое-либо принимающее состояние. Вы не показываете все переходы и не показываете все состояния в вашем автомате.

Вы можете использовать теорему Myhill-Nerode, чтобы определить, сколько состояний имеет минимальный DFA для вашего языка. Заметим, что к пустому состоянию может быть добавлена ​​либо пустая строка, либо b, либо ab, чтобы получить строку на языке; a может быть добавлено b; и b можно добавить пустую строку. Ничего нельзя добавить к aa, bb или ba, чтобы получить строку на языке (поэтому они неразличимы); но к ab может быть добавлена ​​пустая строка (поэтому она неотличима от b).

Определенные таким образом классы эквивалентности соответствуют состояниям в минимальном ДКА. Наши классы эквивалентности:

1. Строки, подобные пустой строке
2. Строки типа b
3. Строки типа a
4. Строки типа aa

Заметим, что b находится в языке, поэтому второй класс будет соответствовать принимающему состоянию. Мы заметили, что ничего нельзя добавить к aa, чтобы получить строку на языке, поэтому этот класс соответствует мертвому состоянию в DFA. Мы записываем переходы между этими состояниями, видя, в какой новый класс эквивалентности нас помещает добавление нового символа:

1. Добавление a помещает нас в (3), так как добавление a к пустой строке дает a, которое находится в (3). Добавление b помещает нас в (2), так как добавление b к пустой строке дает b, которое находится в (2)

2. Добавление a помещает нас в (4), так как добавление a к b дает ba, что похоже на aa в том смысле, что это не префикс какой-либо строки в языке. Добавляя b, мы приходим к (4) с помощью аналогичных рассуждений.

3. Добавляя a, мы получаем aa и находимся в (4). Добавляя b, мы получаем ab, что похоже на b, поэтому мы находимся в (2).

4. Все переходы из мертвого состояния возвращаются в мертвое состояние; оба a и b ведут обратно к (4).

В итоге вы получите что-то вроде:

q1 --a--> q3
 |        /|
 b  --b--< a
 | /       |
 vv        v
q2 -a,b-> q4 \
           ^ a,b
           \_/

Или в табличной форме:

q    s    q'
==   =    ==
q1   a    q3
q1   b    q2
q2   a    q4
q2   b    q4
q3   a    q4
q3   b    q2
q4   a    q4
q4   b    q4

я думаю, что этот DFA является правильным для этого языка.