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

Словарь (алфавит) (V) – конечное непустое множество символов (элементов). Элементы – буквы, слова, образы, математические знаки и др.

Цепочка w – конечная последовательность символов. Цепочки образуются с помощью конкатенаций (объединений). |w| - длина цепочки.

Язык – множество всех цепочек в словаре w, задающееся грамматикой.

Формальная грамматика – система правил, порождающая все цепочки языка и только их. Виды:

• Распознающие – для любой распознаваемой цепочки она решает, является ли эта цепочка правильной с точки зрения конкретного языка.
• Порождающие – может построить любую правильную цепочку.
• Преобразующие – для любой правильной цепочки строит её отображение в виде правильной цепочки.

Грамматика G = (T, N, P, S), где

• T – терминальный (основной) словарь – конечное непустое множество символов (знаков). Из этих символов строятся языковые цепочки.
• N – нетерминальный (вспомогательный) словарь – конечное непустое множество символов. Эти вспомогательные символы обозначают классы исхода.
• V – полный словарь – объединение N и T.
• P – конечное непустое множество правил вывода (продукций)
• S – начальный символ (цель грамматики, аксиома) – выделенный нетерминальный символ, который означает класс языковых объектов, для которых предназначена данная грамматика.

«φ → ψ» означает «заменить на». w’ считается выводимой из w если w=α1φα2; w’=α1ψα2

Длина вывода – число применений правил вывода.

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

Морфема – элементарная единица слова.

Нетерминальные символы – названия классов слов или словосочетаний.

Пример

Пусть множество T = {несёт, тащит, торт, контейнер, портфель, человек, весёлый, грустный, странный}

N = {С (существительное), П (подлежащее), О (определение), Д (дополнение), ГС (группа сказуемого), ГП (группа подлежащего), ПР (предложение)}

ПР = (ГП)(ГС)
ГП = (О)(П)
ГС = (С)(Д)
О = (…)
П = (человек, ребёнок)
С = (…)
Д = (торт, контейнер, портфель)

Можно представить в виде дерева:

• ПР
  • ГП (группа подлежащего)
    • О (…)
    • П (…)
  • ГС (группа сказуемого)
    • С (…)
    • Д (…)

Оно удовлетворяет следующим условиям:

1. Каждая вершина имеет в качестве метки символ из алфавита V.
2. Корень дерева имеет метку S.
3. Если вершина с меткой D имеет хотя бы одну подчинённую вершину, то она принадлежит множеству нетерминальных символов.
4. Если некоторые N вершин с метками {Д1, … Дn} непосредственно подчинены вершине с меткой Д, то в P существует правило вида Д → {Д1, …, Дn}

Маркер структуры составляющих (s-маркер) – структурное дерево.

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

• Грамматики типа 0. Нет ограничений на правила вывода φ→ψ ( φ и ψ — произвольные цепочки из словаря V)
• Грамматики типа 1 (контекстные, контекстно-зависимые, КЗ). Правила удовлетворяют условиям:

​ φ = φ1 А φ2
​ ψ = φ1 ω φ2

• Грамматики типа 2 (контекстно-свободные, КС). A → w. (w-непустая из словаря V, А ∈ N).
• Грамматики типа 3 (автоматные, регулярные). Также называются языки, ими порождаемые. В них нет цепочек, содержат только правила вида

A → aB; A → b; a,b ∈ T; A,B ∈ N

Неукорачивающая грамматика — грамматика, для любого правила которой длина исходной цепочки не превосходит длину порождённой:

φ → ψ: |φ| ≤ |ψ|