Может ли кто-нибудб посказать какдолжен вести себя НКА в созданный по регулярному выражению:
((a*)*)

Автомат строится такой:


3,1,2,4 — состояние с е(пустыми)-переходами
0 — из него астомат выходит только при получении 'а'

Он "напускается" на текст: bcdbcdbcd — тоесть в тексте 'а' не встречается не разу.
Автомат не находит a и из состояние 1 всегда переходит в сосояние 2. Состояние 2 — это внешняя (...)* операция, которая ни очем не догадываясь переходит снова в состояние 1 и т.д. Автомат зацикливается. Как можно решить данную проблемму? Может ли кто что посоветовать?

Зацикливание происходит и в такой ситуации:
автомат: ((first|third)*|second)*
строка: firstsecondfirstsecondttt

Здравствуйте, Acid the Programmer, Вы писали:

ATP>Зацикливание происходит и в такой ситуации:
ATP>автомат: ((first|third)*|second)*
ATP>строка: firstsecondfirstsecondttt

на картинке пометки дуг не хватает
а вообще алгоритм построения НКА по рег выражению см. ахо, сети, ульман: построение компиляторов (если память не изменяет), твой близко не совсем похож на то, что должнО быть

Здравствуйте, Acid the Programmer, Вы писали:

ATP>Может ли кто-нибудб посказать какдолжен вести себя НКА в созданный по регулярному выражению:
ATP>((a*)*)

ATP>Автомат строится такой:
ATP>

ATP>3,1,2,4 — состояние с е(пустыми)-переходами
ATP>0 — из него астомат выходит только при получении 'а'

ATP>Он "напускается" на текст: bcdbcdbcd — тоесть в тексте 'а' не встречается не разу.
ATP>Автомат не находит a и из состояние 1 всегда переходит в сосояние 2. Состояние 2 — это внешняя (...)* операция, которая ни очем не догадываясь переходит снова в состояние 1 и т.д. Автомат зацикливается. Как можно решить данную проблемму? Может ли кто что посоветовать?

А каким алгоритмом ты пользуешься для маделирования этого НКА?
по идее никакого зацикливания не должно быть...

для твоего НКА:

строка: bc
начальное состоняние: e-closure({3}) = {1, 2, 4}
S = e-closure({3})
b = getchar()
foreach a in string do
T = move(S, a);
S = e-closure(T);
a = getchar();
done

if S in F then OK
else FAIL

т.е. последовательность такая
S = {1, 2, 4}

a = 'b'
T = {1,2}
S = {1,2}

a = 'c'
T = {1,2}
S = {1,2}

состояния {0} нету в итоговом S, значит строка
не подходит.


Если не хочется строить все возможные множества, то советую
подумать над преобразованием НКА -> ДКА

Здравствуйте, aka50, Вы писали:

A>А каким алгоритмом ты пользуешься для маделирования этого НКА?
A>по идее никакого зацикливания не должно быть...

A>для твоего НКА:

A>строка: bc
A>начальное состоняние: e-closure({3}) = {1, 2, 4}
A>S = e-closure({3})
A>b = getchar()
A>foreach a in string do
A> T = move(S, a);
A> S = e-closure(T);
A> a = getchar();
A>done

A>if S in F then OK
A> else FAIL

A>т.е. последовательность такая
A>S = {1, 2, 4}

A>a = 'b'
A>T = {1,2}
A>S = {1,2}

A>a = 'c'
A>T = {1,2}
A>S = {1,2}

A>состояния {0} нету в итоговом S, значит строка
A>не подходит.


A>Если не хочется строить все возможные множества, то советую
A>подумать над преобразованием НКА -> ДКА

Дело в том, что я только начал разбираться с регулярными выражениями. Вот написал программу, которая рисует граф по заданному регулярному выражению. У меня пока реализованы 3 основные операции: Concat, Union и Star. С помощью них можно выразить все остальные. Для построения автомата я использую алгоритм Томсона (помоему так). Автомат получается с так называемыми Е-состояниями.
Загвоздка у меня получилать при разборе строки по этому автомату. Вообще с автоматами я работал, но с Детерминированными (сам только узнал, что они так называются) все было ОК. Но с этим E-HKA (НКА с пустыми состояниями) я пока запутался.
Не мог бы ты мне пояснить сам принцип разбора строка по E-HKA и можно поподробней что это за функции такие move и e-closure? (вообще я в интернете где то читал о таких, но слишком уж заумно и сухо было написано, и поэтому я так и не понял зачем они нужны).

Здравствуйте, Acid the Programmer, Вы писали:

ATP>Дело в том, что я только начал разбираться с регулярными выражениями. Вот написал программу, которая рисует граф по заданному регулярному выражению. У меня пока реализованы 3 основные операции: Concat, Union и Star. С помощью них можно выразить все остальные. Для построения автомата я использую алгоритм Томсона (помоему так). Автомат получается с так называемыми Е-состояниями.
ATP>Загвоздка у меня получилать при разборе строки по этому автомату. Вообще с автоматами я работал, но с Детерминированными (сам только узнал, что они так называются) все было ОК. Но с этим E-HKA (НКА с пустыми состояниями) я пока запутался.

дык по этому ДКА и предпочтительнее НКА. Там е-переходов нет, по этому все гораздо проще . Еще и путь из стартового состояния для символа a всегда один.

ATP>Не мог бы ты мне пояснить сам принцип разбора строка по E-HKA и можно поподробней что это за функции такие move и e-closure? (вообще я в интернете где то читал о таких, но слишком уж заумно и сухо было написано, и поэтому я так и не понял зачем они нужны).

http://www.citforum.ru/programming/theory/serebryakov/3.shtml

move(S, a) — это подмножество узлов, достижимых из S при входном символе a
e-closure(T) — это подмножество узлов достижимых из Т через e-переходы
S и T — это подмножества состояний автомата.

А вообще почитать бы тебе чтонить... я не сильно этим
интересовался, но например у Альфреда Ахо "Компиляторы: принципы, технологии, иструменты"
все достаточно толково рассказывается.

Здравствуйте, Acid the Programmer, Вы писали:

ATP>Не мог бы ты мне пояснить сам принцип разбора строка по E-HKA и можно поподробней что это за функции такие move и e-closure? (вообще я в интернете где то читал о таких, но слишком уж заумно и сухо было написано, и поэтому я так и не понял зачем они нужны).

e-closure(s) (e-замыкание(s)) — множество состояний НКА, достижимых из состояния s только по e-переходам.
e-closure(T) (e-замыкание(T)) — множество состояний НКА, достижимых из какого-либо состояния s из множества T только по e-переходам.
move(T,a) — множество состояний НКА, в которые имеется переход из какого-либо состояния s из множества T по входному элементу a.

Перед тем, как рассматривать первый входной элемент, НКА может быть в любом из состояний множества e-closure(s0), где s0 — стартовое состояние НКА. Предположим, что состояния множества T, и только они, достижимы из s0 после прочтения данной последовательности входных элементов, и пусть а — следующий входной символ. Получив а, НКА может переместиться в любое состояние из множества move(T,a). Совершив из этих состояний все возможные e-переходы, НКА после обработки a может быть в любом состоянии из e-closure (move(T,a)).

Если неформально, то идея e-замыкания (e-closure) заключается в том, что мы смотрим, какие состояния доступны из некоторого состояния (или множества состояний), если перед получением символа строки разрешается сколько угодно раз пройти по e-переходам. Естественно, при этом надо запоминать уже посещенные e-переходы, чтобы не попасть в цикл из e-переходов. Может оказаться, что для какого-то символа из очередного состояния возможно несколько достижимых состояний (поэтому КА и называется недетерминированным). Если просто надо ответить на вопрос "сопоставляется/не сопоставляется", то можно сделать, как написано у aka50. Если надо находить границы подвыражений (a-la сохраняющие скобки в Perl), то не обойтись без стека и перебора с возвратом. В этом случае уже не оперируют множествами состояний в явном виде, а рассматривают достижимость состояний по очередному символу строки. В стек информация заносится в том случае, когда в какой-то момент переход по символу неоднозначен, чтобы потом можно было вернуться и перейти по этому же символу в другое состояние из множества возможных.

Здравствуйте, aka50, Вы писали:

A>дык по этому ДКА и предпочтительнее НКА. Там е-переходов нет, по этому все гораздо проще . Еще и путь из стартового состояния для символа a всегда один.
Для сопоставления — да, а вот если надо сохранять границы подвыражений, то сил ДКА не хватит
Простой пример: (A*)A

Здравствуйте, aka50, Вы писали:

A>http://www.citforum.ru/programming/theory/serebryakov/3.shtml

A>move(S, a) — это подмножество узлов, достижимых из S при входном символе a
A>e-closure(T) — это подмножество узлов достижимых из Т через e-переходы
A>S и T — это подмножества состояний автомата.

Спасибо большое за ссылочку и за коментарии по поводу move и e-closure — буду читать и разбираться...
Правда всеравно пока не совсем понятно, но ща на бумажке попробую прикинуть.

А вообще нормально ты так, не сильно этим интересовался, а про move и e-closure знаешь, а я сильно этим интересуюсь и пока никак не могу допетрить Ну да ладно.....

A>А вообще почитать бы тебе чтонить... я не сильно этим
A>интересовался, но например у Альфреда Ахо "Компиляторы: принципы, технологии, иструменты"
A>все достаточно толково рассказывается.

Да у меня Книга "Дракона" есть... я читаю, но неподготовленному человеку, уж слишком тяжело идет.
Хотельсь бы побольше примеров и спросить если что неукого.

Здравствуйте, conraddk, Вы писали:

C>Здравствуйте, Acid the Programmer, Вы писали:

ATP>>Не мог бы ты мне пояснить сам принцип разбора строка по E-HKA и можно поподробней что это за функции такие move и e-closure? (вообще я в интернете где то читал о таких, но слишком уж заумно и сухо было написано, и поэтому я так и не понял зачем они нужны).

C>e-closure(s) (e-замыкание(s)) — множество состояний НКА, достижимых из состояния s только по e-переходам.
C>e-closure(T) (e-замыкание(T)) — множество состояний НКА, достижимых из какого-либо состояния s из множества T только по e-переходам.
C>move(T,a) — множество состояний НКА, в которые имеется переход из какого-либо состояния s из множества T по входному элементу a.

C>Перед тем, как рассматривать первый входной элемент, НКА может быть в любом из состояний множества e-closure(s0), где s0 — стартовое состояние НКА. Предположим, что состояния множества T, и только они, достижимы из s0 после прочтения данной последовательности входных элементов, и пусть а — следующий входной символ. Получив а, НКА может переместиться в любое состояние из множества move(T,a). Совершив из этих состояний все возможные e-переходы, НКА после обработки a может быть в любом состоянии из e-closure (move(T,a)).

C>Если неформально, то идея e-замыкания (e-closure) заключается в том, что мы смотрим, какие состояния доступны из некоторого состояния (или множества состояний), если перед получением символа строки разрешается сколько угодно раз пройти по e-переходам. Естественно, при этом надо запоминать уже посещенные e-переходы, чтобы не попасть в цикл из e-переходов. Может оказаться, что для какого-то символа из очередного состояния возможно несколько достижимых состояний (поэтому КА и называется недетерминированным). Если просто надо ответить на вопрос "сопоставляется/не сопоставляется", то можно сделать, как написано у aka50. Если надо находить границы подвыражений (a-la сохраняющие скобки в Perl), то не обойтись без стека и перебора с возвратом. В этом случае уже не оперируют множествами состояний в явном виде, а рассматривают достижимость состояний по очередному символу строки. В стек информация заносится в том случае, когда в какой-то момент переход по символу неоднозначен, чтобы потом можно было вернуться и перейти по этому же символу в другое состояние из множества возможных.

Так я собственно так и хотел сделать. Я срою НКА для того, что бы можно было бы подвыражения запоминать. У меня 2 стека, для отката состояний и позиции символа в строке.

Так вот хотелось бы получить формальное описание алгоритма, в частности что делать с Е состояниями?
Типа:
Мы находимся в состоянии 3, затем проверяем то-то и то-то и т.д. По ДКА я бегать умею, а как быть с Е состояниями? Можно пояснить на примере мной нарисованного автомата? Хотелось бы применить второй алгоритм, с стеком и возвратами.

Здравствуйте, Acid the Programmer, Вы писали:

ATP>Так я собственно так и хотел сделать. Я срою НКА для того, что бы можно было бы подвыражения запоминать. У меня 2 стека, для отката состояний и позиции символа в строке.

ATP>Так вот хотелось бы получить формальное описание алгоритма, в частности что делать с Е состояниями?
ATP>Типа:
ATP>Мы находимся в состоянии 3, затем проверяем то-то и то-то и т.д. По ДКА я бегать умею, а как быть с Е состояниями? Можно пояснить на примере мной нарисованного автомата? Хотелось бы применить второй алгоритм, с стеком и возвратами.

В стек надо записывать не только состояние и позицию — как минимум еще номер последнего рассмотренного варианта при неоднозначности. Если нужны сохраняющие скобки, то алгоритм усложнится, потому что помимо простого построения e-замыкания надо будет запоминать цепочки скобок, пройденных перед тем, как мы пришли в состояние, принадлежащее e-замыканию. При построении скобки расставляются на переходах НКА. При сопоставлении, как вариант, класть информацию о скобках в стек.

— Находимся в состоянии s, позиция в строке pos.
— Если строка кончилась, проверяем, является ли s конечным. Да — сопоставление удалось, нет — возврат по стеку.
— Берем очередной символ строки a = input[pos], строим e-замыкание для состояния s. Обозначим его E = e-closure(s).
— Строим множество состояний, достижимых из E по символу a. Обозначим его M = move(E, a).
— Если множество пустое, то сопоставление в этой ветке не удалось. Возврат по стеку.
— Если в множестве больше 1 элемента, заносим в стек информацию для возврата (pos, s, номер рассмотренного варианта из M — сейчас это 1).
— Переходим в состояние M[1], увеличиваем позицию в строке на 1.

Как осуществляется возврат по стеку:
— Если стек пустой — сопоставление не удалось.
— Берем со стека pos, s, i
— Строим для s и input[pos] множества E и M (здесь можно соптимизировать, если не перестраивать каждый раз, а кэшировать).
— Если i равно количеству элементов M (рассмотрены все варианты для этой ветки перебора), возврат по стеку еще раз.
Иначе кладем на стек (pos, s, i+1), переходим в состояние M[i+1], увеличиваем позицию в строке на 1.

Дополнение
Алгоритм приведен для проверки соответствия всей строки рег. выражению.
Если надо искать подстроки, алгоритм следует модифицировать: проверять конечное состояние не только при окончании строки, но и при любой ошибке сопоставления, когда предполагается возврат. Ну и с началом строки то же самое — сопоставлять не только с первого символа, а при ошибке пробовать с разных.

Здравствуйте, conraddk, Вы писали:

C>Дополнение
C>Алгоритм приведен для проверки соответствия всей строки рег. выражению.
C>Если надо искать подстроки, алгоритм следует модифицировать: проверять конечное состояние не только при окончании строки, но и при любой ошибке сопоставления, когда предполагается возврат. Ну и с началом строки то же самое — сопоставлять не только с первого символа, а при ошибке пробовать с разных

Понял. Спасибо большое. Ясности добавилось. Теперь вроде в голове мой автомат не зацикливается. Ща буду пытаться запрограммировать. Если что напишу...

Все!!! Спасибо всем огромное, кто помогал. Все работает теперь зацикливания нет.