В описании XML EBNF-ом, w3c используюет, как я понял, собстенное расширение EBNF — исключение: здесь
A — B matches any string that matches A but does not match B.
Как его можно преобразовать в BNF? Или в NFA автомат?
Здравствуйте, vf, Вы писали:
vf>A — B matches any string that matches A but does not match B. vf>Как его можно преобразовать в BNF? Или в NFA автомат?
А в чем проблема? Автомат для этого выражения -- это D(A x NOT B). x здесь обозначает произведение автоматов, NOT -- отрицание, а D -- диагональ произведения.
Произведение строится на цепочках из пар символов, т.е. на элементах декартова произведения алфавитов автоматов. Диагональ произведения -- это пары вида (a,a) для некоторого символа a \in A V B, т.е. пары, где оба компонента совпадают. Отрицание автомата строится просто -- все недопускающие состояния объявляем допускающими и наоборот, каждое допускающее объявляем недопускающим. В общем, идея в том, чтобы запустить A и B параллельно на каждой входной цепочке и допускать только такие из них, на которых автомат A переходит в допускающие состояния, а автомат B -- нет.
Здравствуйте, mefrill, Вы писали:
M>Автомат для этого выражения -- это D(A x NOT B). x здесь обозначает произведение автоматов, NOT -- отрицание, а D -- диагональ произведения.
А где это можно почитать, желательно онлайн? Нашел только формальное описание произведения здесь
Здравствуйте, mefrill, Вы писали:
M>А в чем проблема? Автомат для этого выражения -- это D(A x NOT B). x здесь обозначает произведение автоматов, NOT -- отрицание, а D -- диагональ произведения.
Я правильно понимаю, что диагональ произведения автоматов, дает нам автомат с тем же алфавитом что и исходные, который принимает только такую последовательность, которую принимают оба исходных автомата?
Здравствуйте, vf, Вы писали:
vf>Я правильно понимаю, что диагональ произведения автоматов, дает нам автомат с тем же алфавитом что и исходные, который принимает только такую последовательность, которую принимают оба исходных автомата?
Подробнее. Пусть L(a) обозначает язык автомата A, т.е. то множество цепочек, которое этим автоматов допускается.
Исходная задача сводится к двум:
1. Для автомата B получить автомат, который допускает -L(B), т.е. дополнение языка L(B). Эта задача стандартная, надо просто инвертировать состояния исходного автомата: каждое допускающее сделать недопускающим, а каждое недопускающее -- допускающим. Тогда, любая цепочка, которая недопускается автоматом B, станет допускаться автмоматом -B. с другой стороны, если цепочка допускается автоматом B, то при ее чтении он переходит в недопускающее состояние, а значит, в недоспускающее состояние автомата -B. Иначе говоря, дополнение автматного языка является автоматным языком.
2. Найти автомат, который допускает пересечение языков автоматов A и -B. Основная идея такого автомата -- это запуск параллельно двух автоматов и допуск цепочки только тогда, когда автматы при чтении цепочки одновременно переходят в допускающие состояния. Но понятие "параллельно" в контексте автоматов и их языков непонятно, надо сконструировать новый автомат, который инкапсулирует идею параллельного запуска в себе. Для этого вводят автомат, который работает не на одной цепочке, а на цепочке из пар символов. Пара в данном случае обозначает как раз, что автоматы запускаются на двух цепочках одновременно. Пары -- это декартово произведение, т.е. мы берем цепочки над алфавитом Sigma(A) X Sigma(B), где Sigma(A) и Sigma(B) -- алфавиты языков соответствующих автоматов. Состояния автомата -- пары состояний исходных автоматов, допускающие из них -- пары из допускающих состояний. На вход этому автомату подается последовательность пар символов, но нам необходимо выполнить требование, что пары в этой цепочке должны формироваться из одних и тех же символов, тогда это будет соответстовать нашей идее запуска двух автоматов на одной цепочке. Т.е. из всех пар мы должны выбрать только те, у которых первый и второй компоненты равны, т.е. диагональ декартова произведения. Эта самая диагональ есть то же самое, что и сама цепочка.
Спасибо, за подробный комментарий. Я пытаюсь просчитать пример, в общем получается похоже, но неразбериха с принимающими сомтояниями — принмает ту цепочку, которую не должен. Может поможете найти ошибку?
В исходной рфц-шке густо и часто встречаются выражения типа:
X = C* — C* abc C*
где С — условно, любой символ. Алфавит я принимаю за {a,b,c}
Задача, сделать ДКА для этого выражения.
Первым шагом, делаю NFA для (C*) и (C* abc C*), зелененьким отмечены принимающие состояния до всех преобразований (без дополнения)
Вторым шагом, получаю произведения автоматов, строго не судите — не знаю как оформомляется.
На третьем шаге, NFA автомат произведения, с переименоваными узлами, и вычищеными переходами.
Далее, переход к ДКА, условно(для правильно работы алгоритма нужно разобраться с принимающими состояниями) минимизация — автомат после минимизации мне нравиться, похоже на правду, только получить принимающие состояния, как закрашено, не получается. Если сделать -(C* abc C*) то приниющими состояниями к автомате произведения станут состояния 1,2,3 (по третьей картинке). А если, я нигде не накосячил, то при переходе к ДКА принимающими станут все его состояния, если хотя бы состояние 1 в НКА (рис.3) будет принимающим (оно присутсвует во множествах при переходе к ДКА).
Смотрю на автомат на рис.3, если даже к ДКА не переходить, а "запустить" НКА то одна из "паралельностей" всегда будет в состоянии 1, так что видать произведением автоматов там что-то не так? Ед-но как можно выкрутиться, сделать 4-ое состояние "непринимающим" — то есть если туда попал, то последовательность не принята — но это как-то криво и неправильно.
Здравствуйте, vf, Вы писали:
vf>Первым шагом, делаю NFA для (C*) и (C* abc C*), зелененьким отмечены принимающие состояния до всех преобразований (без дополнения)
Здесь корректно.
vf>Вторым шагом, получаю произведения автоматов, строго не судите — не знаю как оформомляется.
Прежде, чем делать произведение, надо взять отрицание второго автомата, т.е. инвертировать состояния. Получится от что:
Исходный автоматы (допускающие состояния отмечены звездочкой, начальные -- стрелкой):
a b c
-> *0 {0} {0} {0}
a b c
-> 0 {0,1} {0} {0}
1 {} {2} {}
2 {} {} {3}
*3 {3} {3} {3}
Инвертируем допускающие состояния:
a b c
->*0 {0,1} {0} {0}
*1 {} {2} {}
*2 {} {} {3}
3 {3} {3} {3}
Теперь можно взять произведение. Т.к. берем диагональ, не используем пары символов, а сами символы:
a b c
->*{0,0} {{0,0},{0,1}} {{0,0}} {{0,0}}
*{0,1} {} {{0,2}} {}
*{0,2} {} {} {{0,3}}
{0,3} {{0,3}} {{0,3}} {{0,3}}
vf>На третьем шаге, NFA автомат произведения, с переименоваными узлами, и вычищеными переходами.
Соответственно, переименуем состояния:
a b c
->*0 {0,1} {0} {0}
*1 {} {2} {}
*2 {} {} {3}
3 {3} {3} {3}
Здесь последнюю строку можно смело убрать, т.к. к допускающему состоянию она не ведет, т.е. на язык автомата никакого влияния не оказывает, но с методической точки зрения полезно посмотреть полную генерацию.
Автомат недетерминированный, надо его преобразовать в ДКА методом конструкции подмножеств и ленивым вычислением. Идем от нулевого состояния, получаем автомат:
a b c
->*{0} {0,1} {0} {0}
*{0,1} {0,1}} {0,2} {0}
*{0,2} {0,1} {0} {0,3}
{0,3} {0,1,3} {0,3} {0,3}
{0,1,3} {0,1,3} {0,2,3} {0,3}
{0,2,3} {0,1,3} {0,3} {0,3}
Семантика автомат простая: в состояниях {0}, {0,1} и {0,2} он ожидает строки abc, а когда ее находит, то переходит во вторую группу состояний и бесцельно ходит по ним до конца цепочки, т.к. все равно в первую группу перейти не может. Если бы мы сократили последнюю строку, то не было бы перехода а {0,3} из {0,2} и автомат бы останавливался, не дочитав входную строку. Вообще, конечно так не делается, необходимо оставить состояние, в которое будет переход, если строка не допущена, -- т.н. допуск по состоянию вместо допуска по прочитанной цепочке. Вообще, алгоритм минимизации по числу состояний эти холостые хождения уберет.
Здравствуйте, mefrill, Вы писали:
M>Соответственно, переименуем состояния: M>
M> a b c
->>*0 {0,1} {0} {0}
M> *1 {} {2} {}
M> *2 {} {} {3}
M> 3 {3} {3} {3}
M>
До сих пор полностью согласен, если я состояния пронумерую с нуля, у нас все совпадает.
M>Автомат недетерминированный, надо его преобразовать в ДКА методом конструкции подмножеств и ленивым вычислением. Идем от нулевого состояния, получаем автомат:
А вот здесь не согласен, каким образом выбраны принимающие состояния в ДКА? Сам ДКА такой же как у меня (особо не вникая). При переходе к ДКА принимающими состояниями становяться те в подможестве которых присутствует хотя бы одно принимающие состояние НКА. А в НКА 0-состояние принмающее, оно присутствует во всех подможествах, значит все состояния ДКА должны быть принимающими.
M>
Здравствуйте, vf, Вы писали:
vf>А вот здесь не согласен, каким образом выбраны принимающие состояния в ДКА? Сам ДКА такой же как у меня (особо не вникая). При переходе к ДКА принимающими состояниями становяться те в подможестве которых присутствует хотя бы одно принимающие состояние НКА. А в НКА 0-состояние принмающее, оно присутствует во всех подможествах, значит все состояния ДКА должны быть принимающими.
Ну да, здесь я запарился немного. На самом деле, во всех этих манипуляциях для данной регулярки нет никакого смысла, т.к. оба автомата любую цепочку над данным алфавитом допускают. Выражение C* abc C* некорректно в том смысле, который в него вкладывается, т.к. первое C* содержит abc. Правильно надо написать (C* — abc) abc C*.
Спасибо за помощь.
M>Ну да, здесь я запарился немного. На самом деле, во всех этих манипуляциях для данной регулярки нет никакого смысла,
Можно было расматривать такой вариант, если бы я взял этот пример с потолка. Но подобные выражения, присутствуют в рфц-шке по xml (линк есть в первом посте).
M>т.к. оба автомата любую цепочку над данным алфавитом допускают. M> Выражение C* abc C* некорректно в том смысле, который в него вкладывается, т.к. первое C* содержит abc.
Я трактую выражение таким образом:
C* — все цепочки
C* abc C* — цепочки которые содержат abc
и тогда по A — B matches any string that matches A but does not match B, все выглядит логично — все цепочки которые не содержат abc.
M>Правильно надо написать (C* — abc) abc C*.
Нет, здесь что-то совсем не то, даже если расматривать выражение в скобках и все равно не так, так мы выкинем в скобках только одну строку abc, можно было бы еще расмотреть вариант
C* — C* abc
но учитывая что замыкающая С* (в С* abc C*) может содержать 0 символов, это не принципиальное изменение, так небольшая оптимизация, сути не меняет.
Для этого частного случая, одно решение я нашел, найти пересечение принимающих состояний при произведении автоматов и объявить его "ошибочным" (что в принципе логично), так как "ошибочных" состояний в автомате нет — его следует удалить.
Интересно насколько правочен такой подход в обшем случае?!
10/3/2010 1:26 PM, mefrill пишет: > Здравствуйте, vf, Вы писали: > > vf>А вот здесь не согласен, каким образом выбраны принимающие состояния в ДКА? Сам ДКА такой же как у меня (особо не вникая). При переходе к ДКА принимающими состояниями становяться те в подможестве которых присутствует хотя бы одно принимающие состояние НКА. А в НКА 0-состояние принмающее, оно присутствует во всех подможествах, значит все состояния ДКА должны быть принимающими. > > Ну да, здесь я запарился немного. На самом деле, во всех этих манипуляциях для данной регулярки нет никакого смысла, т.к. оба автомата любую цепочку над данным алфавитом допускают. Выражение C* abc C* некорректно в том смысле, который в него вкладывается, т.к. первое C* содержит abc. Правильно надо написать (C* — abc) abc C*.
По моему, запись L_1 = 'С* abc C*' вполне корректна и задает язык
всех строк содержащих 'abc'. Язык NOT L_1 по идее должен содержать все
строки, которые не содержат подстроку 'abc'. То есть и L_1 и NOT L_1 не
равны 'C*'.
По сути, инвертирование состояний будет работать только для DFA — то
есть в нашем случае нужно привести автомат L_1 к DFA и потом
инвертировать состояния — тогда мы получим NOT L_1.
Для инвертирования же NFA нужно строить дополнение — то есть для
каждого перехода (s_0, C_0_1, s_1) в исходном автомате добавлять (s_0,
C*\C_0_1, s_1) в NOT автомат.
Здравствуйте, ettcat, Вы писали:
E>10/3/2010 1:26 PM, mefrill пишет:
E> По сути, инвертирование состояний будет работать только для DFA — то E>есть в нашем случае нужно привести автомат L_1 к DFA и потом E>инвертировать состояния — тогда мы получим NOT L_1.
Теперь можно поменять final/non final состояния, и получим NOT(C* abc C*), он же C* — (C* abc C*).
E> Для инвертирования же NFA нужно строить дополнение — то есть для E>каждого перехода (s_0, C_0_1, s_1) в исходном автомате добавлять (s_0, E>C*\C_0_1, s_1) в NOT автомат.
Сам же чушь спорол — это тоже только для DFA сработает.
Здравствуйте, ettcat, Вы писали:
E>> По сути, инвертирование состояний будет работать только для DFA — то E>>есть в нашем случае нужно привести автомат L_1 к DFA и потом E>>инвертировать состояния — тогда мы получим NOT L_1.
Можете дать ссылку на авторитетный источник? Может книгу, нашел хорошую подборку по автомато-строению.
E> Теперь можно поменять final/non final состояния, и получим NOT(C* abc C*), он же C* — (C* abc C*).
Выглядит верно, ед-но мне такой подход не очень подходит. С частями NFA удобно работать линкуя их эпсилон переходами, а в ДКА все сложнее, трудно будет разобрать какие состояния нужно инвертировать в нем когда отрицание маленький его кусочек, и таких отрицаний может быть несколько. Хотелось бы решить все эти вопросы в NFA, раз существует решение для ДКА ожидаемо должно быть и для НКА. Хотя как вариант, можно перейти к ДКА, инвертировать принимающие состояния, "преобразовать" его в НКА и продолжить строительство НКА.
E>>> По сути, инвертирование состояний будет работать только для DFA — то E>>>есть в нашем случае нужно привести автомат L_1 к DFA и потом E>>>инвертировать состояния — тогда мы получим NOT L_1.
vf>Можете дать ссылку на авторитетный источник?
По сути, вы уже доказали на примере, что простое инвертирование состояний в NFA не работает.
Спасибо, буду разбираться.
