Союз языков, принятых FSA, без переходов эпсилон

Я пытался формализовать объединение двух автоматов с конечным состоянием без использования эпсилон-переходов. Я хочу создать новое начальное начальное состояние для новых автоматов и из этого нового начального состояния создать переходы в достижимые состояния из начального состояния отдельных автоматов, скопировав эти переходы.

Учитывая FSA

M1 = <Σ1, Q_1, q0_1, ->_1>

где Σ1 = алфавит, Q_1 — набор состояний, q0_1 — начальное состояние, а ->_1 — переходы M1.

Учитывая другой FSA

 M2 = <Σ2, Q_2, q0_2, ->_2>

где Σ2 — алфавит, Q_2 — набор состояний, q0_2 — начальное состояние, а ->_2 — переходы M2.

Теперь я определил FSA M+ = M1 ∪ M2 как FSA:

 M_+ = <Σ+, Q_+, q0_+, ->_+>
 Σ+ = Σ1 ∪ Σ2 - alphabet of both
 Q_+ = Q_1 ∪ Q_2 ∪ {q0_+},
 q0+ is the new initial start state 
 ->_+ = ->_1 ∪ ->_2 ∪ ->_C

Я обнаружил проблемы с определением ->_C - новых переходов в достижимые состояния M1 и M2. Я определил тип ->_C следующим образом: Q x 2^Σ x 2^Q. Это должен быть набор, однако я не уверен, как определить его формально. Любая помощь будет очень признательна.

введите здесь описание изображения


css discrete-mathematics finite-automata automata
person Andre Croucher    schedule 04.05.2017    source источник
comment
Вам нужна машина M+ такая, что L(M+) = L(M1) U L(M2), или что-то еще? stackoverflow.com/a/7798776/847269 отвечает на ваш вопрос?   -  person Patrick87    schedule 05.05.2017
comment
Привет, спасибо за ответ. Я просто хотел бы знать, как определить переходы из нового начального состояния в состояния M1 и M2, скопировав их переходы из предыдущих начальных состояний (q0_1 и q0_2)   -  person Andre Croucher    schedule 06.05.2017

Ответы (1)


arrow_upward
1
arrow_downward

Почему Q x 2 ^ Σ x 2 ^ Q ? Лучше Q x Σ x 2 ^ Q; переходы определяются отдельно для каждой возможной буквы. В противном случае вы не знаете, какое состояние принадлежит какой букве (буквам).

->C := { (q0+,x,P) : (q0_1,x,P) \in ->_1 OR (q0_2,x,P) \in ->_2 }

person Peter Leupold    schedule 08.05.2017
comment
Привет, спасибо за ответ, я хотел бы иметь определение, подходящее для переходов для автомата на изображении, прикрепленном выше. Моя попытка была следующей: --->C = {(q0_+, A, q1) | (q0_1,A,q2) \in -›_1 AND (q0_1,B,q2) \in -›_2}..... однако моя проблема в том, что это не обрабатывает как A, так и B, а только A. - person Andre Croucher; 15.05.2017
comment
Будьте осторожны с тем, что является переменной, а что буквой. На вашей диаграмме буквы А и В. В моем определении -›_C x является переменной и, таким образом, обрабатывает все буквы. Ваша версия здесь, в комментарии, немного неясна. Никаких переходов из q0_1 в q_2 в ->_2 быть не может, потому что состояния от первого автомата. Если вы хотите использовать буквы вместо переменных, вам действительно нужно определить набор для каждой буквы отдельно и взять объединение. - person Peter Leupold; 15.05.2017