Грамматика языка и порождающие грамматики. Сказ о «правильных» скобочках⁠⁠

Предыдущая статья: Что такое язык программирования? Не спешим отвечать, знакомимся с определением формальных языков.

Небольшое добавление к предыдущей статье. Запись языка над алфавитом Σ принято записывать так:

L(Σ) = { α, …}

Поставим задачу описать язык «правильных» скобочек, то есть множество всех цепочек, где наши любимые рунетом цепочки символов ))))))))) без открывающих скобочек не входит в этот язык, эх … (((((((((, ну и закрывающих. Но мы то знаем какие «правильные»?

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

Давайте знакомится с формулой порождающей грамматики:

G = (T, N, P, S) - теперь по порядку, что есть что.

Т и N - это алфавиты, Т - основных символов их ещё называют терминалами, а N - вспомогательных символов, нетерминалы.

Немного о значении слова терминал, от лат. terminus — предел, конец.

P - конечное множество правил вывода (переходов), вида: α → β, где α и β цепочки из символов алфавитов Т и N.

S - начальный нетерминал, с чего начинаются все выводы цепочек языка.

Уже появились мысли, как записать язык «правильных» скобочек?

Не мучайтесь, вот ответ: G = ( {(, )}, {S}, {S → (S), S →SS, S → ε}, S)

Пример вывода:

S => (S) => (SS) => ((S)(S)) => (()())

Результат вывода называют сентенцией (от sentence — предложение), то что может предложить наша грамматика.

Итого, таким образом с помощью нашей Gрамматики, мы можем вывести некое множество цепочек (предложений, сентенций) над алфавитом Т, которое составляет наш язык L(T).

А вот о типах грамматик, о тех что Хомски рассказывает, мы поговорим чуть позже. Чтожъ, мои милые братцы и сестрицы, а на том пока.