Понятие языка. Формальное определение языка

В общем случае язык – это заданный набор символов и правил, устанавливаю­щих способы комбинации этих символов между собой для записи осмысленных текстов. Основой любого естественного или искусственного языка является ал­фавит, определяющий набор допустимых символов языка.

Алфавит – это счетное множество допустимых символов языка. Будем обозна­чать это множество символом V. Интересно, что согласно формальному опре­делению, алфавит не обязательно должен быть конечным (перечислимым) мно­жеством, но реально все существующие языки строятся на основе конечных алфавитов.

Цепочка символов α является цепочкой над алфавитом V: α(V), если в нее вхо­дят только символы, принадлежащие множеству символов V. Для любого алфа­вита V пустая цепочка  может как являться, так и не являться цепочкой (V). Это условие оговаривается дополнительно.

Если V – некоторый алфавит, то:

V+ – множество всех цепочек над алфавитом V без ;

V* – множество всех цепочек над алфавитом V, включая .

Справедливо равенство: V* = V+  {}.

Языком L над алфавитом V: L(V) называется некоторое счетное подмножество цепочек конечной длины из множества всех цепочек над алфавитом V. Из этого определения следуют два вывода: во-первых, множество цепочек языка не обяза­но быть конечным; во-вторых, хотя каждая цепочка символов, входящая в язык, обязана иметь конечную длину, эта длина может быть сколь угодно большой и формально ничем не ограничена.

Все существующие языки подпадают под это определение. Большинство реаль­ных естественных и искусственных языков содержат бесконечное множество це­почек. Также в большинстве языков длина цепочки ничем не ограничена (напри­мер, этот длинный текст – пример цепочки символов русского языка). Цепочку символов, принадлежащую заданному языку, часто называют предложением языка, а множество цепочек символов некоторого языка L(V) – множеством предложе­ний этого языка. Для любого языка L(V) справедливо: L(V)  V*.

Язык L(V) включает в себя язык L’(V): L’(V)L(V), если αL(V):
α L’(V). Множество цепочек языка L’(V) является подмножеством множества цепочек языка L(V) (или эти множества совпадают). Очевидно, что оба языка должны строится на основе одного и того же алфавита.

Два языка L(V) и L’(V) совпадают (эквивалентны): L’(V) = L(V), если L’(V)L(V) и L(V)L’(V); или, что то же самое: α L’(V): α L(V) и
α L’(V): α L(V). Множества допустимых цепочек символов для эквивалентных языков должны быть равны.

Два языка L(V) и L’(V) почти эквивалентны: L’(V)  L(V), если L’(V){}= = L(V){}. Множества допустимых цепочек символов почти эквивалентных языков могут различаться только на пустую цепочку символов.

Способы задания языков

Итак, каждый язык – это множество цепочек символов над некоторым алфави­том. Но кроме алфавита язык предусматривает и задание правил построения до­пустимых цепочек, поскольку обычно далеко не все цепочки над заданным алфа­витом принадлежат языку. Символы могут объединяться в слова или лексемы – элементарные конструкции языка, на их основе строятся предложения – более сложные конструкции. И те и другие в общем виде являются цепочками симво­лов, но предусматривают некоторые правила построения. Таким образом, необ­ходимо указать эти правила, или, строго говоря, задать язык.

Язык задать можно тремя способами:

1. Перечислением всех допустимых цепочек языка.

2. Указанием способа порождения цепочек языка (заданием грамматики языка).

3. Определением метода распознавания цепочек языка.

Первый из методов является чисто формальным и на практике не применяется, так как большинство языков содержат бесконечное число допустимых цепочек и перечислить их просто невозможно. Трудно себе представить, чтобы появи­лась возможность перечислить, например, множество всех правильных текстов на русском языке или всех правильных программ на языке Pascal. Иногда, для чисто формальных языков, можно перечислить множество входящих в них цепо­чек, прибегнув к математическим определениям множеств. Однако этот метод уже стоит ближе ко второму способу.

Например, запись L({0,1}) = {0n1n, n > 0} задает язык над алфавитом V = {0,1}, со­держащий все последовательности с чередующимися символами 0 и 1, начинаю­щиеся с 0 и заканчивающиеся 1. Видно, что пустая цепочка символов в этот язык не входит. Если изменить условие в этом определении с n > 0 на n0, то получим почти эквивалентный язык L’({0,1}), содержащий пустую цепочку.

Второй способ предусматривает некоторое описание правил, с помощью кото­рых строятся цепочки языка. Тогда любая цепочка, построенная с помощью этих правил из символов алфавита языка, будет принадлежать заданному языку. На­пример, с правилами построения цепочек символов русского языка вы знакомились в средней школе.

Третий способ предусматривает построение некоторого логического устройства (распознавателя) – автомата, который на входе получает цепочку символов, а на выходе выдает ответ: принадлежит или нет эта цепочка заданному языку. На­пример, читая этот текст, вы сейчас в некотором роде выступаете в роли распо­знавателя.