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

Question

Может ли кто-нибудь сказать мне, соответствует ли прилагаемый DFA?

Я полагаю, чтобы дать DFA для языка, который имеет алфавит Е = {а, Ь}

мне нужно DFA для этого ----> A = {ε, B, AB}

Answer 1

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

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

Что касается первого пункта: начиная с 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).

Соответствующие классы эквивалентности соответствуют состояниям в минимальном DFA. Наши классы эквивалентности:

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 

Answer 2

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