Недавно я задал вопрос по математике SE. Ответа пока нет. Этот вопрос связан с этим вопросом, но с техническими подробностями в отношении информатики.
Даны два DFA и где набор состояний, входной алфавит и функция перехода и одинаковы, начальные состояния и конечные (принимающие) состояния могут быть разными. Пусть и - языки, принятые и соответственно.
Есть четыре случая:
- и .
- и .
- и .
- и .
Мой вопрос
Каковы различия между и в случаях 2, 3 и 4?
У меня есть более конкретный вопрос по этому поводу,
Моноид перехода автомата - это множество всех функций на множестве состояний, индуцированных входными строками. Смотрите страницу для более подробной информации. Моноид перехода можно рассматривать как моноид, действующий на множество состояний. Смотрите эту вики-страницу для более подробной информации.
Во многих литературах автомат называется сильносвязанным, когда действие моноида транзитивно, т. Е. Всегда есть хотя бы один переход (входная строка) из одного состояния в другое состояние.
Если и являются сильно связанными автоматами, каковы различия между и в случаях 2, 3 и 4 выше?
В какой литературе обсуждаются эти вопросы в деталях?
Я искал много книг и статей и пока не нашел ничего полезного. Я считаю, что у меня пока нет подходящих ключевых слов. Таким образом, я ищу помощи. Любые указатели / ссылки будут оценены очень высоко.
Ответы:
Поскольку сильно связаны, то если q 1 ≠ q 2 , существуют слова p 1 , p 2, такие что δ ( q 1 , p 1 ) = q 2 и δ ( q 2 , p 2 ) = q 1 .A,B q1≠q2 p1,p2 δ(q1,p1)=q2 δ(q2,p2)=q1
Рассмотрим случай 2, тогда тогда и только тогда, когда p 2 w ∈ L ( B ) и x ∈ L ( B ) тогда и только тогда, когда p 1 x ∈ L ( A ) . Таким образом, вы можете добавить префикс для переключения между языками.w∈L(A) p2w∈L(B) x∈L(B) p1x∈L(A)
Рассмотрим случай 3, затем снова - с сильной связью там самое большее Слова с 1 , . , , , s k такое, что для каждого q i ∈ F 1 имеем δ ( q i , s i ) ∈ F 2 и аналогично для другого направления (от B к A ).|F1| s1,...,sk qi∈F1 δ(qi,si)∈F2 B A
Таким образом, вы можете составлять суффиксы для переключения между языками.
Комбинируя их, вы можете охарактеризовать различия, используя префиксы и суффиксы. Например, в случае 4, тогда и только тогда, когда p 1 w s i в L ( A ) для некоторого s i в заранее определенном конечном множестве.w∈L(B) p1wsi L(A) si
На самом деле, вы даже можете сказать что-то интересное об этих словах: определите как DFA, где q 1 - начальное состояние, а q 2 - конечное состояние, тогда в случае 2 у вас есть L ( B ) = L ( C ) ⋅ L ( A ) (и аналогично для другого направления).C q1 q2 L(B)=L(C)⋅L(A)
Что касается суффиксов, то здесь все больше, поскольку вы не можете предопределить, в каком конечном состоянии вы закончите. Я не уверен, что вы можете написать это как конкатенацию, но вы можете написать где A q - DFA, полученный из A , задающий F = { q } , и E q является DFA, который начинается в q с конечными состояниями F 2 .L(B)=⋃q∈F1L(Aq)⋅L(Eq) Aq A F={q} Eq q F2
Для случая 4 вы можете объединить два.
Вы можете быть обеспокоены тем, что это не реальный ответ, а скорее просто характеристика свойств с использованием слов, а не состояний, но это типичный ответ в этой области (аналогично теореме Майхилла-Нерода).
источник