В информатике, что НЕ является официальным языком?

Question

На википедии https://www.wikiwand.com/en/Formal_language, я нашел определение формального языка:

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

Это выглядит довольно абстрактно для меня. И я не могу представить какой-либо язык, который не соответствует этому определению. Кто-нибудь есть идеи о том, что неформальный язык выглядит и как он не соответствует определению?

Answer 1

Позвольте мне сначала задать ваш вопрос. Хорошим примером неформального языка являются естественные языки. Примеры на английском и словенском языках. Тагалог и Тарифит бербер. К сожалению, лингвисты, похоже, не имеют определения естественного языка, о котором все согласятся.

Noam Chomsky классно пытался смоделировать естественный язык, используя контекстно-свободные гаммары в своей бумаге 1956 года Three Models for the Description of Language. Он изобрел (или обнаружил, если хотите) их в этой статье; хотя он не называл их так; в то время как они не были полезны для моделирования английского языка, они революционизировали информатику.

Формально официальный язык представляет собой всего лишь набор строк над конечным алфавитом. Вот и все.

Примеры включают все действующие программы на языке C, все допустимые файлы HTML, все допустимые файлы XML, все строки «сбалансированных» круглых скобок (например, (),()(), ((()))()(()), ...), набор (коды под некоторым кодированием) всех детерминированных машин Тьюринга, которые всегда останавливаются, набор всех простых графиков, которые могут быть окрашены в k -colors (на самом деле их коды при некотором кодировании), набор всех двоичных строк, которые заканчиваются и начинаются с 1 и т. д.

Некоторые из них легко распознаются с использованием регулярного выражения (или, что эквивалентно, DFA); некоторые из них невозможно распознать с использованием DFA, но могут быть распознаны с помощью PDA (или, что то же самое, можно описать с помощью контекстно-свободной грамматики); другие не допускают такого описания, но могут быть распознаны машиной Тьюринга; некоторые из них не распознаются даже машиной Тьюринга (называемой бескомпромиссной).

Именно поэтому определение так полезно. Многие вещи, с которыми мы сталкиваемся в CS evey day, можно отнести к формальным языкам.

Для хорошего ознакомления с предметом, я настоятельно рекомендую превосходную книгу Введение в теорию автоматов, языки и вычисления by Hopcroft et al.

Answer 2

Английский не является официальным языком. Это не просто набор строк; у него есть устная форма, и эволюция с течением времени, и диалекты, и всевозможные другие вещи, которых нет у официального языка. Формальный язык не мог получить слово «электронная почта» от одного десятилетия к следующему.

Answer 3

Язык представляет собой набор последовательностей, составленных из заданных символов. Он может быть либо конечным, либо бесконечным (множество английских предложений бесконечно, хотя существуют предложения, например чрезмерно длинные, которые невозможно понять даже носителем языка). Если оно конечно, то любое его описание является формальным определением.

Если язык бесконечен, скажем, язык арифметических выражений, включающий числа, два бинарных оператора '+', '*' и переменные, то вы не можете перечислить все строки, принадлежащие к языку, но иногда (см. комментарий blazs ниже), вы можете дать конечное описание как набор правил.

E: = NUM ​​| v | E '+' E | E '*' E

(где NUM - последовательность цифр, v - переменная) является конечным описанием бесконечного множества. Вот что делает его формальным.

Различные аспекты, такие как речь или эволюция языка, - это разные проблемы. Они также могут быть оформлены.