Есть ли другой способ описать формальный язык, кроме грамматики?

Question

Я ищу математическую теорию, которая занимается описанием формальных языков (набор строк) в целом, а не только грамматическими иерархиями.

Answer 1

Регулярные выражения - это формализм, например, для описания набора языков. Хотя существуют алгоритмы преобразования регулярных грамматик и выражений в обоих направлениях, они по-прежнему представляют собой две разные теории. Кроме того, автоматы (как множественное число автоматов) могут помочь вам описать языки, не только DFA и NFA, которые описывают тот же набор, что и обычные языки, но и 2DFA, стековые автоматы. Например, автомат с двумя стеками такой же мощный, как машина Тьюринга. Наконец, сами машины Тьюринга являются формализмом для языков. Для любой машины Тьюринга набор всех строк, на которых данная машина Тьюринга останавливается на конечном числе шагов, является формально определенным языком.

Answer 2

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

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