Может ли RegEx с отрицательным прогнозом быть представлен как конечный автомат?

Question

Я работаю над инструментом для манипуляции с контекстно-свободными языками, и внутреннее представление грамматики хранится как конечный автомат. Заглядывая дальше в EBNF и RegEx, я узнал, что у EBNF есть "исключения", а у RegEx - негативные перспективы. Я могу видеть, как они могут быть смоделированы симметричной разностью NFA, но подозревал, что они выходят за пределы возможностей обычного DFA или NFA.

Но потом я наткнулся на это, что довольно ясно говорит о том, что я был неправ. Может кто-нибудь указать на бесплатный ресурс, который может показать, как преобразовать EBNF с исключениями или RegEx с негативным прогнозом, в DFA?

Answer 1

Вы можете заменить отрицательный прогноз положительным прогнозом на полный набор возможных совпадений минус отрицательный прогноз. Например, если бы мы работали с одиночными символами az в качестве области соответствия, /what(?!n) такой же как /what(?=[a-mo-z])/, Это нормально в теории, но не так здорово на практике при работе с большими матчами, например /afraid of (?!chinese)/,

https://cs.stackexchange.com/questions/2557/how-to-simulate-backreferences-lookaheads-and-lookbehinds-in-finite-state-auto дает хороший подход к преобразованию lookahead в нечто, похожее на DFA, с важное предостережение в конце.