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