Язык шаблонов (формальные языки) - Pattern language (formal languages)

В теоретическая информатика, а язык шаблонов это формальный язык который можно определить как набор всех частных экземпляров нить констант и переменных. Языки шаблонов были представлены Дана Англуин в контексте машинное обучение.[1]

Определение

Для конечного множества Σ из постоянный символы и счетное множество Икс из Переменная символы, не пересекающиеся с Σ, a шаблон конечный непустой нить символов из Σ∪Икс. длина шаблона п, обозначаемый |п|, это просто количество его символов. Множество всех паттернов, содержащих ровно п различные переменные (каждая из которых может встречаться несколько раз) обозначается пп, набор всех паттернов на всех п*.A замена это отображение ж: п* → п* такой, что[примечание 1]

Если п = ж(q) для некоторых шаблонов п, q ∈ п* и некоторая замена ж, тогда п как говорят менее общий, чем q, написано п≤q, в этом случае обязательно |п| ≥ |q| держит.Для шаблона п, это язык определяется как набор всех менее общих шаблонов, которые формально построены только из констант: L(п) = { s ∈ Σ+ : s ≤ п }, куда Σ+ обозначает множество всех конечных непустых строк символов из Σ.

Например, используя константы Σ = {0, 1} и переменные Икс = { Икс, у, z, ...}, образец 0Икс10хх1 ∈п1 и xxy ∈п2 имеет длину 7 и 3 соответственно. Экземпляр первого шаблона - 00z100z0z1 и 01z101z1z1, он получается заменой, отображающей Икс до 0z и к 1z, соответственно, и символ друг друга. Оба 00z100z0z1 и 01z101z1z1 также являются экземплярами xxy. Фактически, L(0Икс10хх1) является подмножеством L(xxy). Язык выкройки Икс0 и Икс1 - это набор всех битовых строк, которые обозначают четное и нечетное двоичное число, соответственно. Язык хх - это набор всех строк, которые можно получить путем объединения битовой строки с самой собой, например 00, 11, 0101, 1010, 11101110 ∈ L(хх).

Характеристики

NP-жесткость принадлежности к языку шаблонов снижение от НП-полный 1-из-3-SAT проблема: Учитывая CNF из м статьи с п переменные, шаблон длины 3п+4м+1 с 2п переменные и строка длины 4п + 5м+1 можно построить, как показано (м= 3 и п= 4 в примере). Переменные в верхнем регистре в шаблоне соответствуют инвертированным переменным в CNF. Строка соответствует шаблону тогда и только тогда, когда существует такое присвоение, что в каждом предложении ровно один литерал равен 1 (что означает "истинный"в CNF). В левой части, например" 0wW0 соответствует "01110", только если один из ш,W соответствует "1" (соответствует "ложный"), а другой -" 11 "(соответствует"истинный"), т.е. если ш соответствует отрицанию W. В правой части, например "0xYZ0 соответствует "011110", только если точно один из Икс,Y,Z соответствует "11", а остальным - "1", т.е. если ровно один литерал соответствует "истинный".

Проблема определения того, действительно ли s ∈ L(п) для произвольной строки s ∈ Σ+ и узор п является НП-полный (см. рисунок), и, следовательно, проблема решения п ≤ q для произвольных шаблонов п, q.[2]

Класс языков шаблонов не закрыто под ...

  • союз: например для Σ = {0,1} как над, L(01)∪L(10) не является языком шаблонов;
  • дополнение: Σ+ \ L(0) не является языком шаблонов;
  • пересечение: L(Икс0у)∩L(Икс1у) не является языком шаблонов;
  • Клини плюс: L(0)+ не является языком шаблонов;
  • гомоморфизм: ж(L(Икс)) = L(0)+ не является языком шаблонов, предполагая ж(0) = 0 = ж(1);
  • обратный гомоморфизм: ж−1(111) = {01, 10, 000} не является языком шаблонов, предполагая ж(0) = 1 и ж(1) = 11.

Класс языков шаблонов закрыто под ...

  • конкатенация: L(п)⋅L(q) = L(п⋅q);
  • разворот: L(п)rev = L(пrev).[3]

Если п, q ∈ п1 шаблоны, содержащие ровно одну переменную, тогда п ≤ q если и только если L(п) ⊆ L(q); такая же эквивалентность имеет место для образов одинаковой длины.[4]Для выкроек разной длины над пример п = 0Икс10хх1 и q = xxy показывает, что L(п) ⊆ L(q) может иметь место, не подразумевая п ≤ q.Однако любые два шаблона п и q, произвольной длины, генерируют один и тот же язык тогда и только тогда, когда они равны с точностью до согласованного переименования переменных.[5]Каждый узор п это общее обобщение всех строк на его сгенерированном языке L(п) по модулю ассоциативности (⋅).

Расположение в иерархии Хомского

В изысканном Иерархия Хомского, класс языков шаблонов является надлежащим суперклассом и подклассом одноэлементного[заметка 2] и проиндексированные языки соответственно, но несравнимо с языковыми классами между ними; из-за последнего класс языка шаблонов явно не отображается в таблице ниже.

Класс языков шаблонов несравним с классом языков. конечные языки, с классом обычные языки, и с классом контекстно-свободные языки:

  • язык шаблонов L(хх) не является контекстно-независимым (следовательно, ни обычный ни конечный ) из-за лемма о накачке;
  • конечный (следовательно, также регулярный и контекстно-свободный) язык {01, 10} не является языком шаблонов.

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

Каждый язык шаблонов может быть создан индексированная грамматика: Например, используя Σ = { а, б, c } и Икс = { Икс, у },шаблон а Икс б у c Икс а у б порождается грамматикой с нетерминальными символами N = { SИкс, Sу, S } ∪ Икс, терминальные символы Т = Σ, индексные символы F = { аИкс, бИкс, cИкс, ау, бу, cу }, начальный символ SИкс, и следующие производственные правила:

SИкс[σ]→ SИкс[аИкс σ]| SИкс[бИкс σ]| SИкс[cИкс σ]| Sу[σ]
Sу[σ]→ Sу[ау σ]| Sу[бу σ]| Sу[cу σ]| S[σ]
S[σ]→ а Икс[σ] б у[σ] c Икс[σ] а у[σ] б
Икс[аИкс σ]→ аИкс[σ]у[аИкс σ]→у[σ]
Икс[бИкс σ]→ бИкс[σ]у[бИкс σ]→у[σ]
Икс[cИкс σ]→ cИкс[σ]у[cИкс σ]→у[σ]
Икс[ау σ]→Икс[σ]у[ау σ]→ ау[σ]
Икс[бу σ]→Икс[σ]у[бу σ]→ бу[σ]
Икс[cу σ]→Икс[σ]у[cу σ]→ cу[σ]
Икс[]→ εу[]→ ε

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

SИкс[]  ⇒   SИкс[бИкс]  ⇒   SИкс[аИкс бИкс]  ⇒   Sу[аИкс бИкс]  ⇒   Sу[cу аИкс бИкс]  ⇒   S[cу аИкс бИкс]  ⇒   а Икс[cу аИкс бИкс] б у[cу аИкс бИкс] c Икс[cу аИкс бИкс] а у[cу аИкс бИкс] б  ⇒   а Икс[аИкс бИкс] б у[cу аИкс бИкс] c Икс[cу аИкс бИкс] а у[cу аИкс бИкс] б  ⇒   а а Икс[бИкс] б у[cу аИкс бИкс] c Икс[cу аИкс бИкс] а у[cу аИкс бИкс] б  ⇒   а ab Икс[] б у[cу аИкс бИкс] c Икс[cу аИкс бИкс] а у[cу аИкс бИкс] б  ⇒   а ab б у[cу аИкс бИкс] c Икс[cу аИкс бИкс] а у[cу аИкс бИкс] б  ⇒ ... ⇒   а ab б c у[] c Икс[cу аИкс бИкс] а у[cу аИкс бИкс] б  ⇒   а ab б c c Икс[cу аИкс бИкс] а у[cу аИкс бИкс] б  ⇒ ... ⇒   а ab б c c ab Икс[] а у[cу аИкс бИкс] б  ⇒   а ab б c c ab а у[cу аИкс бИкс] б  ⇒ ... ⇒   а ab б c c ab а c у[] б  ⇒   а ab б c c ab а c б

Точно так же грамматика индекса может быть построена на основе любого шаблона.

Образцы обучения

Учитывая набор образцов S струн, узор п называется описательный из S если S ⊆ L(п), но нет S ⊆ L(q) ⊂ L(п) для любого другого шаблона q.

Учитывая любой набор образцов S, описательный шаблон для S можно вычислить

  • перечисление всех паттернов (вплоть до переименования переменных) не длиннее самой короткой строки в S,
  • выбирая из них шаблоны, которые генерируют надмножество S,
  • выбирая из них выкройки максимальной длины, и
  • выбирая из них шаблон, минимальный по ≤.[6]

На основе этого алгоритма класс языков шаблонов может быть выявлено в пределе из положительных примеров.[7]

Примечания

  1. ^ Представление Англуина о замещении отличается от обычного представления о замещении. подстановка строк.
  2. ^ т.е. языки, состоящие из одной строки; они соответствуют прямолинейные грамматики

Рекомендации

  1. ^ Дана Англуин (1980). «Поиск общих шаблонов для набора строк». Журнал компьютерных и системных наук. 21: 46–62. Дои:10.1016/0022-0000(80)90041-0.
  2. ^ Теорема 3.6, стр.50; Следствие 3.7, стр.52
  3. ^ Теорема 3.10, стр.53
  4. ^ Лемма 3.9, стр.52; Следствие 3.4, с.50
  5. ^ Теорема 3.5, стр.50
  6. ^ Теорема 4.1, стр.53
  7. ^ Дана Англуин (1980). «Индуктивный вывод формальных языков из положительных данных» (PDF). Информация и контроль. 45 (2): 117–135. Дои:10.1016 / с0019-9958 (80) 90285-5.; здесь: Пример 1, стр.125