Как в регулярных выражениях выглядит NFA для оператора "^"?т.е. "a" но не "b"

С операторами:

"|" 

"?" 

"*" 

"+" 

все просто и понятно, а вот как быть с оператором "^"?

В гугле пусто, т.к. корректно сформулировать вопрос так и не удалось(NFA operator ^, NFA operator not, NFA ^)???

Это сообщение отредактировал(а) rudvil - 25.7.2010, 15:05

В таблице состояний отрицательное и положительное меняется местами.

А никак, тут для упрощение отрицательные состояния не показаны.
И вообще оператор ^  обычно применяется только в "[]" скобках.

первый раз слышу, пошел гуглить...
все равно, спасибо.

Гугл тебя думать не научит.

Вот так думаю все станет понятно:

a(∑\{b})

Когда ∑ обозначает весь алфавит:

∑={a..z}U{0..9}U{@#$%^&*...}

Добавлено через 4 минуты и 56 секунд

Это лишено всякого смысла, ибо если а, то уж точно не б. Видимо имеется в виду: а, а потом все кроме б. Именно для этого случая я написал пояснение.

Правильный ответ:

1) Имея НФА, строишь ДФА ему эквивалентный
2) Имея ДФА строишь его отрицание, посредством инверсии конечных состояний.
3) Полученный ДФА он же и НФА и есть нот от исходного автомата

esperanto, А побыстрее никак?

Чтобы упростить я остановился на решении как тут http://www.codeproject.com/KB/recipes/re_e...ion_parser.aspx

т.е. если попали на dummy то дальше идти не будем.

На курсе, вычислений учили именно так делать. Я не видел других решений в учебниких никогда. 

rudvil, Да, но если мне нужно построить не отрицание одного символа, а отрицание целого регулярного выражения, то такой фокус не пройдет.

Добавлено через 54 секунды
Кстати, за ссылку спасибо. Интересно было почитать. Жаль я не читал ее до того, как реализовал свой регексп.

esperanto, У меня не получилось реализовать такой вариант. 
Вот посмотри на этот регексп комментария в С например: "/*"(^("*/"))*"*/"
Здесь я выделил операторы красным. ^ - отрицание. * - Kleene closure (хрен знает как по-русски, ну сколько угодно повторений включая 0). Скобки задают приоритеты операторов. Можно прочитать этот регексп как: "/*"; все, что угодно кроме "*/"; "*/". Именно так задают подобные токены в Лексе и подобных тулах.

Нарисуй или опиши мне автомат, который принимает комментарии. Внимание! До комментария и после идут другие токены, т.е. мне необходим именно такой автомат, который бы мне нарезал ввод на токены, один из которых - комментарий.

Не совсем верное рег. выражение.
Тут можно почитать про более универсальный регэксп http://ostermiller.org/findcomment.html


Это сообщение отредактировал(а) rudvil - 2.11.2010, 23:32

В формальном определение регулярных выражений нет операции отрицание. Отрицание можно применить на язык распозноваемый регулярным выражением.

Замыкание Клина наверное это называется

Известно, что регулярные языки можно инвертировать и получить регулярный язык. В данном случае регулярное выражение - пример нотации. Дело в принципе. Как можно автомат такой создать?

Тогда наверное так

Разбираем регулярное выражение.
Находим терм содержащий отрицание.
Переводим его в автомат, для автомата строим отрицание, и ответ переводим в регулярное выражение. это регулярное выражение подставляем вместо терма и так продолжаем


Сложность экспоненциальная.