Разница между языками, принятыми двумя DFA с разными начальными состояниями / принимающими государствами?

9

Недавно я задал вопрос по математике SE. Ответа пока нет. Этот вопрос связан с этим вопросом, но с техническими подробностями в отношении информатики.

Даны два DFA A=(Q,Σ,δ,q1,F1) и где набор состояний, входной алфавит и функция перехода и одинаковы, начальные состояния и конечные (принимающие) состояния могут быть разными. Пусть и - языки, принятые и соответственно.B=(Q,Σ,δ,q2,F2)ABL1L2AB

Есть четыре случая:

  1. q1=q2 и .F1=F2
  2. q1q2 и .F1=F2
  3. q1=q2 и .F1F2
  4. q1q2 и F1F2 .

Мой вопрос

Каковы различия между L1 и L2 в случаях 2, 3 и 4?

У меня есть более конкретный вопрос по этому поводу,

Моноид перехода автомата - это множество всех функций на множестве состояний, индуцированных входными строками. Смотрите страницу для более подробной информации. Моноид перехода можно рассматривать как моноид, действующий на множество состояний. Смотрите эту вики-страницу для более подробной информации.

Во многих литературах автомат называется сильносвязанным, когда действие моноида транзитивно, т. Е. Всегда есть хотя бы один переход (входная строка) из одного состояния в другое состояние.

Если и являются сильно связанными автоматами, каковы различия между и в случаях 2, 3 и 4 выше?ABL1L2

В какой литературе обсуждаются эти вопросы в деталях?

Я искал много книг и статей и пока не нашел ничего полезного. Я считаю, что у меня пока нет подходящих ключевых слов. Таким образом, я ищу помощи. Любые указатели / ссылки будут оценены очень высоко.

scaaahu
источник
Что вы подразумеваете под «чем отличаются»? Вы хотите знать, могут ли / должны отличаться и в случаях 2,3,4? L1L2
Хендрик Ян
@HendrikJan Если вы прочитаете ответ Шаула, приведенный ниже, вы поймете, что и могут различаться. (Он использовал и ). Я не знаю, должны ли они отличаться. Это часть моего вопроса. Я спросил «в чем различия?». Я не подразумевал, что они должны отличаться. L 2L1L2L ( B )L(A)L(B)
scaaahu

Ответы:

8

Поскольку сильно связаны, то если q 1q 2 , существуют слова p 1 , p 2, такие что δ ( q 1 , p 1 ) = q 2 и δ ( q 2 , p 2 ) = q 1 .A,Bq1q2p1,p2δ(q1,p1)=q2δ(q2,p2)=q1

Рассмотрим случай 2, тогда тогда и только тогда, когда p 2 w L ( B ) и x L ( B ) тогда и только тогда, когда p 1 x L ( A ) . Таким образом, вы можете добавить префикс для переключения между языками.wL(A)p2wL(B)xL(B)p1xL(A)

Рассмотрим случай 3, затем снова - с сильной связью там самое большее Слова с 1 , . , , , s k такое, что для каждого q iF 1 имеем δ ( q i , s i ) F 2 и аналогично для другого направления (от B к A ).|F1|s1,...,skqiF1δ(qi,si)F2BA

Таким образом, вы можете составлять суффиксы для переключения между языками.

Комбинируя их, вы можете охарактеризовать различия, используя префиксы и суффиксы. Например, в случае 4, тогда и только тогда, когда p 1 w s i в L ( A ) для некоторого s i в заранее определенном конечном множестве.wL(B)p1wsiL(A)si

На самом деле, вы даже можете сказать что-то интересное об этих словах: определите как DFA, где q 1 - начальное состояние, а q 2 - конечное состояние, тогда в случае 2 у вас есть L ( B ) = L ( C ) L ( A ) (и аналогично для другого направления).Cq1q2L(B)=L(C)L(A)

Что касается суффиксов, то здесь все больше, поскольку вы не можете предопределить, в каком конечном состоянии вы закончите. Я не уверен, что вы можете написать это как конкатенацию, но вы можете написать где A q - DFA, полученный из A , задающий F = { q } , и E q является DFA, который начинается в q с конечными состояниями F 2 .L(B)=qF1L(Aq)L(Eq)AqAF={q}EqqF2

Для случая 4 вы можете объединить два.

Вы можете быть обеспокоены тем, что это не реальный ответ, а скорее просто характеристика свойств с использованием слов, а не состояний, но это типичный ответ в этой области (аналогично теореме Майхилла-Нерода).

Shaull
источник
p1p1δ(q1,p1)=q2L(A)L(B)
Я отредактировал ответ с более точной информацией.
Шаул
C
Пожалуйста, обратите внимание на дополнительные изменения в посте.
Шаул
1
Хорошая идея. Вы принимаете одно окончательное состояние за раз, затем принимаете союз. Надеюсь, моя интерпретация верна.
scaaahu