Я ищу математические теории, которые имеют дело с описанием формальных языков (набор строк) в целом, а не только грамматических иерархий.
22
Я ищу математические теории, которые имеют дело с описанием формальных языков (набор строк) в целом, а не только грамматических иерархий.
Ответы:
Есть много возможностей. Другие уже упоминали автоматы, которые предлагают богатый выбор. Рассмотрим также следующие рамки:
Некоторые языки могут быть определены непосредственно (со) индуктивными определениями . Например, наименьшая точка фиксации - это тот же язык, который описан , самая большая точка фиксации - . Обратите внимание, что такое определение также может быть записано в форме исчисления или правила вывода :aw ∈ La w ∈ La⇒ ε∈L ⇒ a w ∈ L⇒baw∈L
(ba∣a)∗ (ba∣a)ω
aε,весш,шб а Wa
(ba∣a)∗(ba∣a)ω
Слова определяют структуры слов, которые можно использовать в качестве моделей логической формулы . По сути, каждое слово определяет область своих позиций , предикаты так что для всех , предикат то есть < из 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 } пa( я ) ⟺wя= а a ∈ Σ < < N Dвес су : Dвес× Dвес→{0,1} это верно тогда и только тогда, когда второй параметр является прямым преемником первого. w=aababaab aSw⊨∀i.∀j. (Pb(i) ∧ suc(i,j))→¬Pb(j);a
( b a ∣ a )* ω ( b a ∣ a )ω a□( Pб→ ◯ ( ¬ Pб) )a ω
Так, например, если то на самом деле, эта формула первого порядка определяет - через набор всех структур слов, которые ее выполняют - тот же язык, что и , Соответствующие -языка описывается формулой LTL
(ba∣a)∗ω(ba∣a)ω
ω
Известно несколько эквивалентов между классами классического языка и некоторыми логиками. Например, FO соответствует языкам без звезд, слабый MSO - обычным языкам, а MSO - -регулярным языкам. Смотрите здесь для ссылок.
Что-то ортогональное классическим классам - это языковые шаблоны . Предположим, что конечный алфавит и переменный алфавит . Строка называется шаблоном . Пусть множество подстановок. Мы определяем язык шаблона как Обратите внимание, что расширена для работы с шаблонами; Терминальные символы остаются без изменений. В качестве примера рассмотримX = { x 1 , x 2 , … } p ∈ ( Σ ∪ X ) + H = { σ ∣ σ : X → Σ ∗ } pΣ Икс= { х1,x2, ...} p ∈ ( Σ ∪ X)+ H ={σ|σ:X→ Σ*} п aL (p)={σ(p)∣σ∈H}.a
σ
L(x1abbax1)={wabbaw∣w∈{a,b}∗} .
σл(х1ЬЬх1)={швЬЬш|ш∈{,Ь}*}
Обратите внимание, что мы допускаем замены для удаления переменных; некоторые свойства класса языков шаблонов сильно отличаются для удаления и удаления без удаления. Языки паттернов представляют особый интерес в изучении стиля Gold .
источник
Вы должны взглянуть на теорию автоматов . Об этом много материала.
Например, вы можете определить обычный язык с недетерминированным конечным автоматом с помеченными ребрами: строка принадлежит языку, если автомат может следовать переходам, помеченным его символами, и останавливается в конечном состоянии.
Кроме того, контекстно-свободная грамматика может быть распознана автоматом .
Другой способ определения языков - с помощью машин Тьюринга .
источник
Из иерархии Хомского существует четыре типа формальных языков (каждый из них является подмножеством языков после него):
Регулярный формальный язык может быть описан:
1., 2. и 3. эквивалентны, и из одного вы можете построить другие.
Не зависящий от контекста формальный язык может быть описан следующим образом:
Также 1. и 2. эквивалентны.
Контекстный формальный язык может быть описан:
Перечислимый формальный язык может быть описан:
источник
В дополнение к другим ответам можно описать и классифицировать языки с точки зрения «генераторов» и свойств замыкания. Например, имеет смысл говорить о наименьшем AFL, генерируемом каким-либо языком. Хорошее место, чтобы начать изучать этот тип описания - эта книга, хотя может быть довольно сложно найти ее печатную копию.
источник