Существуют ли другие способы описания формальных языков, кроме грамматики?

22

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

mtanti
источник
Обратите внимание, что существует много, много типов грамматики помимо классических Chomsky, например множественные , связанные и зависящие от длины грамматики, не зависящие от контекста, соответственно (легко гуглируемые)
Рафаэль

Ответы:

14

Есть много возможностей. Другие уже упоминали автоматы, которые предлагают богатый выбор. Рассмотрим также следующие рамки:

  1. Некоторые языки могут быть определены непосредственно (со) индуктивными определениями . Например, наименьшая точка фиксации - это тот же язык, который описан , самая большая точка фиксации - . Обратите внимание, что такое определение также может быть записано в форме исчисления или правила вывода :
    (baa)(baa)ωa εLвесLaвесLaвесLбaвесLa
    (бa|a)*(бa|a)ω
    aε,весaвес,aвесбaвесa

  2. Слова определяют структуры слов, которые можно использовать в качестве моделей логической формулы . По сути, каждое слово определяет область своих позиций , предикаты так что для всех , предикат то есть < из N, ограниченный D w, и предикат suc : D w × D w{ 0 , 1 }P a : D { 0 , 1 } P a ( i ) w i = a a Σ < w = a a b a b a a b bDвесзнак равно{1,...,N}пa:D{0,1}Pa(я)весязнак равноaaΣ<<NDвесsuc:Dw×Dw{0,1}это верно тогда и только тогда, когда второй параметр является прямым преемником первого.
    Так, например, если то на самом деле, эта формула первого порядка определяет - через набор всех структур слов, которые ее выполняют - тот же язык, что и , Соответствующие -языка описывается формулой LTLw=aababaab
    (baa)ω(baa)ωaSwя,J, (пб(я)  SUC(я,J))¬пб(J);a
    (бa|a)*ω(бa|a)ω
    ωa(пб(¬пб))a
    Известно несколько эквивалентов между классами классического языка и некоторыми логиками. Например, FO соответствует языкам без звезд, слабый MSO - обычным языкам, а MSO - -регулярным языкам. Смотрите здесь для ссылок.ω

  3. Что-то ортогональное классическим классам - это языковые шаблоны . Предположим, что конечный алфавит и переменный алфавит . Строка называется шаблоном . Пусть множество подстановок. Мы определяем язык шаблона как Обратите внимание, что расширена для работы с шаблонами; Терминальные символы остаются без изменений. В качестве примера рассмотримX = { x 1 , x 2 , } p ( Σ X ) + H = { σ σ : X Σ } pΣX={x1,Икс2,...}п(ΣИкс)+ЧАСзнак равно{σ|σ:ИксΣ*}п
    σл(х1ЬЬх1)={швЬЬш|ш{,Ь}*}aL(p)={σ(p)σH}.a
    σ
    L(x1abbax1)={wabbaww{a,b}} .
    Обратите внимание, что мы допускаем замены для удаления переменных; некоторые свойства класса языков шаблонов сильно отличаются для удаления и удаления без удаления. Языки паттернов представляют особый интерес в изучении стиля Gold .

Рафаэль
источник
5

Вы должны взглянуть на теорию автоматов . Об этом много материала.

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

Кроме того, контекстно-свободная грамматика может быть распознана автоматом .

Другой способ определения языков - с помощью машин Тьюринга .

Риккардо Т.
источник
5

Из иерархии Хомского существует четыре типа формальных языков (каждый из них является подмножеством языков после него):

Регулярный формальный язык может быть описан:

  1. Регулярная грамматика
  2. Конечный автомат (детерминированный / недетерминированный)
  3. Регулярное выражение

1., 2. и 3. эквивалентны, и из одного вы можете построить другие.

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

  1. Контекстная грамматика
  2. Pushdown автомат

Также 1. и 2. эквивалентны.

Контекстный формальный язык может быть описан:

  1. Линейный ограниченный автомат (машина Тьюринга с ограниченной лентой)

Перечислимый формальный язык может быть описан:

  1. Общая машина Тьюринга
Антон
источник
И все остальные языковые классы?
Рафаэль
А бесклассовые языки?
Дейв Кларк,
Хомский не говорит, что это единственные типы языков - он считает, что это всего лишь четыре типа, и мы по-прежнему считаем их важными, но есть много других типов.
reinierpost
5

В дополнение к другим ответам можно описать и классифицировать языки с точки зрения «генераторов» и свойств замыкания. Например, имеет смысл говорить о наименьшем AFL, генерируемом каким-либо языком. Хорошее место, чтобы начать изучать этот тип описания - эта книга, хотя может быть довольно сложно найти ее печатную копию.

Сэм Джонс
источник