Здравствуйте, 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 -- нет.