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

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

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

:

_и цепочки символов. Способы задания языков

у _ некоторый алфавит, то:

у+ — множество всех цепочек над алфавитом V без X;

V* — множество всех цепочек над алфавитом V, включая X. Справедливо равенство: V* = V⁺ u {А.}. Языком L над алфавитом V: L(V) называется некоторое счетное подмножество

почек конечной длины из множества всех цепочек над алфавитом V. Из этого

_{деления} следуют два вывода: во-первых, множество цепочек языка не обяза-

о быть конечным; во-вторых, хотя каждая цепочка символов, входящая в язык,

обязана иметь конечную длину, эта длина может быть сколь угодно большой и

формально ничем не ограничена.

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

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

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

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

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

каждый язык — это множество цепочек символов над некоторым алфави­том. Но кроме алфавита язык предусматривает и задание правил построения до-/стимых цепочек, поскольку обычно далеко не все цепочки над заданным алфа­витом принадлежат языку. Символы могут объединяться в слова или лексемы — лементарные конструкции языка, на их основе строятся предложения — более ложные конструкции. И те и другие в общем виде являются цепочками симво-i но предусматривают некоторые правила построения. Таким образом, необ-°Димо указать эти правила, или, строго говоря, задать язык. ^ЗЬ1к задать можно тремя способами:

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

казанием способа порождения цепочек языка (заданием грамматики языка). Определением метода распознавания цепочек языка. ■

350 Глава 9. Формальные языки и грамматики

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

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

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

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

Дата добавления: 2015-06-27