Первоначально наука о языках – лингвистика – сводилась к изучению конкретных естественных языков, их классификации, выяснению сходств и различий между ними. Возникновение и развитие математики, изучающей языки, проведение работ по изучению средств коммуникации животных и другие исследования привели в 30-х годах ХХ в. к существенно более широкому представлению о языке, при котором под языком понимается всякое средство общения, состоящее из [ 1 ]:

· знаковой системы, т.е. множества допустимых последовательностей знаков;

· множества смыслов этой системы;

· соответствия между последовательностями знаков и смыслами, делающего «осмысленными» допустимые последовательности знаков.

Знаками могут быть буквы алфавита, математические обозначения, звуки и т.д. Математическая лингвистика рассматривает только такие знаковые системы, в которых знаками являются символы некоторого алфавита, а последовательностями знаков – тексты, т.е. языки рассматриваются как произвольные последовательности осмысленных текстов. При этом правила, определяющие множество текстов, образуют синтаксис языка, а описание множества смыслов и соответствия между смыслами и текстами – семантику языка. Семантика языка зависит от характера объектов, описываемых языком, и средства ее изучения различны для различных типов языков. Синтаксис же языка, как оказалось, в меньшей степени зависит от содержания и назначения языка.

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

Буква (или символ) – это простой неделимый знак, множество букв образует алфавит. Алфавиты являются множествами, и поэтому к ним можно применять теоретико-множественные обозначения. В частности, если A и B такие алфавиты, что АВ, то будем говорить, что А является подалфавитом В.

Цепочка – упорядоченная последовательность букв алфавита. Пусть А — алфавит, тогда цепочки одинаковой длины являются элементами множества: А_n=А×А×…×А и записываются в виде: а₁ а₂ … а_n, а не (а₁, а₂, …, а_n), как это принято для обозначения элементов декартового произведения множеств. Буквы также являются цепочками для случая n = 1.

Цепочка может и не иметь букв, тогда это — пустая цепочка, будем обозначать эту цепочку символом . При этом не является буквой, т.е.  А.

Цепочки будем называть также словами.

Множество всех возможных цепочек (слов) над алфавитом А называют замыканием А и обозначают А*, так что

А* = А⁰UА¹U…= Аⁿ,  здесь А⁰ = {}, А¹ = А.

Множество А* называют итерацией алфавита А. Множество непустых цепочек (слов) над алфавитом А (усеченная итерация алфавита А) определяется как:

А⁺ = А* {} =  Аⁿ.

Каждая цепочка  А* имеет конечную длину, которая обозначается через || и равна числу букв , при этом || = 0.

Цепочки могут образовывать последовательности цепочек. Для этих целей используется бинарная операция над цепочками, которая называется конкатенацией. Операция конкатенации обозначается знаком , определяется на множестве А* следующим образом: если ,  А*, то , т.е. результатом выполнения операции является цепочка и сразу же за ней записанная цепочка . Операция  ассоциативна, но не коммуникативна. При этом  =  = для любых цепочек и || = || + ||.

Если цепочки состоят из повторяющихся букв, то применяются сокращенные обозначения, чтобы показать, что цепочку нужно рассматривать как произведение букв алфавита. Поэтому, например, с помощью буквы xА можно образовать цепочки  = х⁰, хх = х², хх^n-1= хⁿ и т.д. Это же используется для обозначения повторяющихся цепочек: например, цепочку хухух можно записать как х(ух)² или (ху)²х, при этом символы (,)А.

При преобразовании одних цепочек в другие используется понятие подцепочки. Пусть ,А*, А – алфавит. Цепочка называется подцепочкой , если = ; ,А*.

Альтернативным набором терминов для буквы, алфавита или цепочки (слова) является набор: слово, словарь и предложение соответственно.

Совокупность цепочек (или предложений) называется языком. Формально язык L над алфавитом А – это множество цепочек А*, поэтому LА*. Следовательно операции над цепочками индуцируют операции на языках. Отсюда получаем:

L⁰ = {}; Lⁿ=L^n-1L, nN, L⁺ = Lⁿ, L^*= Lⁿ.

Используя приведенную выше терминологию, язык программирования для заданного алфавита А является таким подмножеством множества А*, которое включает в себя только те предложения, которые благодаря внешней информации об их семантике считаются осмысленными, т.е. удовлетворяют синтаксису языка программирования.

Проведенное определение формального языка как любого подмножества А* является чересчур общим: оно не позволяет выделять среди множества языков отдельные их классы, которые используются на практике. Выделять такие классы  можно, используя соотношение Туэ (названными так в честь норвежского математика, впервые их использовавшего).

Соотношениями Туэ называют правила, согласно которым любой цепочке  из А* ставится в соответствие цепочка  из того же множества А*(i=1,2, …, n) и наоборот. Соотношения Туэ приводят к так называемым ассоциативным исчислениям [7]. Однако и соотношения Туэ слишком общи, чтобы быть основой исследования таких свойств, как синтаксис языков программирования. Наложение ограничений на правила туэтовских систем – введение односторонних правил, в этом случае их называют полусоотношениями или продукциями (обозначают их ), привело к созданию формального математического аппарата – формальным грамматикам, которые являются, по-существу, полусистемами Туэ, и которые оказались наиболее приемлемым механизмом описания языков программирования.

Теория формальных грамматик занимается описанием, распознаванием и переработкой языков. Она позволяет ответить на ряд прикладных вопросов. Например, могут ли языки из некоторого класса Z распознаваться быстро и просто; принадлежит ли данный язык классу Z; существуют ли алгоритмы, которые давали бы ответ на вопросы типа: «Принадлежит или нет к языку L цепочка ?» и т.д.

В общем случае существуют два основных способа описания отдельных классов языков:

· с помощью порождающей процедуры;

· с помощью распознающей процедуры.

Первая из них задается с помощью конечного множества правил, называемых грамматикой и порождающих в точности те цепочки, которые принадлежат языку L. Вторая – с помощью некоторого абстрактного распознающего устройства (автомата).

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

Перейдем теперь к формальному изложению рассмотренных выше понятий.