Многоязычная минимизация DFA

10

Я заинтересован в небольшом обобщении DFA. Как обычно, мы имеем набор состояний , конечный алфавит , действие определенное на помощью , и начальное состояние ; но вместо обычного терминального множества, мы берем семейство подмножеств . Многоязычный DFA - это кортежQΣΣQδ:Q×ΣQq0(Ti)i1..nQM

(Q,Σ,δ,q0,(Ti))

и распознается если для некоторого . Определите как семейство языков, распознаваемых M, если хотите.LΣML={sΣ|q0sTi}i1..n(Li(M))i1..n

Хорошо, теперь мой вопрос: учитывая семейство регулярных языков , я хочу найти минимальный многоязычный DFA как описано выше, такой, что для все , то есть такие, чтосводится ко всем таким машинам. Мой вопрос: есть ли известные эффективные способы сделать это, возможно, аналогичные стандартной теории минимизации DFA? И наоборот, есть ли доказательства того, что эта проблема может быть сложной?(Li)i1..nMLi=Li(M)i1..n|Q|

gdmclellan
источник
7
Мне кажется, что стандартный алгоритм, основанный на уточнении разбиения, модифицированный только для начала путем разбиения исходного набора состояний по тому, принимают ли они / не принимают для каждого из заданных подмножеств а не для одного набора , должен просто работать немедленно. Почему бы и нет? Он разделяет пары состояний только тогда, когда они должны быть разделены, поэтому он все еще генерирует самое грубое уточнение состояний. TiT
Дэвид Эппштейн
1
Доказательство комментария от @DavidEppstein легко, если вы определите отношение эквивалентности если для каждого , где - отношение эквивалентности Майхилла-Нерода. Затем вы можете продолжить в том же направлении, что и стандартный алгоритм минимизации. xyxTiyixTiy
Шал
не совсем понимаю. Является ли ответом на эту проблему нахождение минимального DFA объединения DFA с одинаковой «настройкой», за исключением разных конечных состояний, каждое DFA для ? Кроме того, определение распознавания , похоже, не имеет смысла, похоже, что это смешивает строки и наборы состояний. 1..nL={...}
13
Замечания Дэвида Эппштейна и Шоулла выглядят убедительно, и я найду время, чтобы пересмотреть теорему Майхилла-Нерода, когда у меня будет время убедить себя, что частное все еще дает минимальный автомат. Оглядываясь назад, это кажется слишком очевидным.
gdmclellan
@vzn: определенно не хочу объединять языки оригинального автомата; и может перекрываться. Многоязычным DFA с языками и должны быть в состоянии отчета, что , например, , но . Что касается нотации, используемой при определении распознавания языка, нотация определяется расширением до действия на по следующим правилам для всех : . TiABsAsBδΣQqQ,σΣ,sΣqσ=δ(q,σ),q(sσ)=(qs)σ
gdmclellan

Ответы:

14

Короткий ответ . Для конечного семейства регулярных языков существует уникальный минимальный детерминированный полный мультиавтомат, распознающий это семейство.L=(Li)1in

Подробности . Случай соответствует стандартной конструкции, и общий случай не сильно отличается по духу. Для языка и слова пусть . Определите отношение эквивалентности на , установив как являются регулярными, это сравнение имеет конечный индекс. Кроме того, легко видеть , что каждый насыщается и что для каждого , означаетn=1Luu1L={vAuvL}A

uvfor each LL, u1L=v1L
LiLiaAuvuava, Обозначим через пустое слово и -класса слова . Пусть будет детерминированным мультиавтоматом, определенным следующим образом:1[u]uAL=(Q,[1],,(Fi)1in)
  1. Q={[u]uA} ,
  2. [u]a=[ua] ,
  3. Fi={[u]uLi} .

По построению, тогда и только тогда, когда и, следовательно, принимает семейство . Осталось доказать, что минимален. На самом деле оно минимально в сильном алгебраическом смысле (что означает, что оно имеет минимальное число состояний). Пусть и два мультиавтомата. Морфизм - это сюръективное отображение из на такое, что[1]uFiuLiALLALA=(Q,q,,(Fi)1in)A=(Q,q,,(Fi)1in)f:AAQQ

  1. f(q)=q ,
  2. для , , 1inf1(Fi)=Fi
  3. для всех и , .uAqQf(qu)=f(q)u

Тогда для любого доступного детерминированного мультиавтомата принимающего , существует морфизм из в . Чтобы доказать это, сначала проверяется, что если , то . Теперь определяется как где - любое слово такое, что . Тогда можно показать, что удовлетворяет трем необходимым свойствам.ALAALqu1=qu2=qu1u2ff(q)=[u]uqu=qf

Конец немного отрывочный, дайте мне знать, если вам нужно больше деталей.

J.-E. Штырь
источник