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

Pzz>Ну и учти еще, что POSIX regexp, из-за возможности ссылаться на уже насканированное, не является регулярным языком по Хомскому, и обычно реализуется в виде автомата с возвратами и стеком состояний.

Насколько я помню, с регвырами несложно построить выражение, которое при реализации через КА построит КА то ли экспоненциального то ли около того размера. В общем большой КА получится. Получается, что НКА в худшем случае долго работает, а КА в худшем случае требует очень много памяти. Ну и НКА более богатый и на практике с вырожденными случаями сталкиваться приходится редко. Поэтому НКА и используют для реализации, хотя есть и реализации на КА, если действительно важна O(N) производительность.