Я полагаю, вы ссылаетесь на «традиционные» текстовые протоколы на основе строк. Например, любой протокол, использующий XML, не является регулярным, поскольку XML не является обычным языком (на самом деле XML не является даже контекстно-свободным, если вы смотрите на уровень отдельных символов). В этом случае я не могу думать о каких-либо нерегулярных протоколах. Наиболее распространенным способом перехода в нерегулярный синтаксис языка является требование, чтобы парсер мог рассчитывать, и мне кажется, что протокол, который потребует такой способности анализировать сообщения, будет просто сложным (например, сопоставление скобки) или ограниченные (например, с помощью явного подсчета вместо того, чтобы разрешать произвольно длинные списки).
Использование BNF, вероятно, потому, что его легко понять как описание синтаксиса, а не потому, что контекстная свобода дает вам необходимую дополнительную мощность. Главным преимуществом, я думаю, является возможность использовать переменные для обозначения общих частей синтаксиса. Если вы посмотрите на BNF в общих спецификациях интернет-протокола, вы заметите, что они действительно используют только функции обычных языков: неограниченное повторение, выбор, опциональность.
Ваше утверждение, относящееся к реализациям протоколов состояний, звучит для меня как некоторое недоразумение. Это не парсер, который реализован как конечный автомат, а механизм протокола, а переходы состояний не запускаются отдельными символами или токенами на входе, а полными сообщениями. Как правило, состояния в государственной машине протокола больше связаны с установлением и срывом связи, чем с фактическим сообщением. Например, конечный автомат TCP имеет 11 состояний, из которых достаточно одного только для установленного соединения, в котором происходит вся фактическая передача данных, а остальные - об открытии и закрытии соединения. (Да, я знаю, что TCP не является текстовым, но это хорошо известный протокол с установленным конечным автоматом, поэтому он служит хорошим примером: на уровне двигателей протокола не имеет значения, является ли синтаксис сообщения текстовым или двоичный.)