Давайте предположим, что у нас есть доступ, встроенный или определенный нами в языке, к следующим предикатам:
Head(x, y) iff y is a list and x is the first element in the list
Tail(x, y) iff x and y are lists and x is the same as y but is missing y's first element
Equal(x, y) iff x and y are the the same thing
Прежде всего, я думаю, ясно, что этот язык может принимать все обычные языки. По теореме Майхилла-Нерода все состояния в минимальном DFA для регулярного языка соответствуют единственному классу эквивалентности при соотношении неразличимости. Кажется, что мы могли бы иметь один предикат на класс / состояние эквивалентности, чтобы представлять, принадлежит ли список, соответствующий входной строке, этому классу, а затем другой предикат, который является истинным, только если один из предикатов, соответствующих принимающему состоянию, является истинным. Таким образом, для языка над {a, b} с четным числом a и нечетным числом b минимальный DFA имеет четыре состояния:
O
|
V
q0<---a--->q1
^ ^
| |
b b
| |
V V
q2<---a--->q3
Здесь q2 является единственным принимающим состоянием. Наша программа DataLog может выглядеть следующим образом:
Q0(()).
Q0(x) :- Head(y, x), Equal(y, 'a'), Tail(z, x), Q1(z).
Q0(x) :- Head(y, x), Equal(y, 'b'), Tail(z, x), Q2(z).
Q1(x) :- Head(y, x), Equal(y, 'a'), Tail(z, x), Q0(z).
Q1(x) :- Head(y, x), Equal(y, 'b'), Tail(z, x), Q3(z).
Q2(x) :- Head(y, x), Equal(y, 'a'), Tail(z, x), Q3(z).
Q2(x) :- Head(y, x), Equal(y, 'b'), Tail(z, x), Q0(z).
Q3(x) :- Head(y, x), Equal(y, 'a'), Tail(z, x), Q2(z).
Q3(x) :- Head(y, x), Equal(y, 'b'), Tail(z, x), Q1(z).
EvenAOddB(x) :- Q2(x).
Основываясь на этом примере, я думаю, ясно, что мы всегда можем кодировать переходы таким образом, и поэтому любой обычный язык может быть принят. Таким образом, DataLog, по крайней мере, столь же мощен, как и детерминированные c конечные автоматы.
Мы можем определить это:
// Last(x, y) iff x is the last element of y
Last(x, y) :- Head(x, y), Tail(z, y), Equal(z, ()).
// AllButLast(x, y) iff x and y are the same list but x is missing the last element of y
AllButLast((), (x)).
AllButLast(x, y) :- Head(w, x), Head(z, y), Equal(w, z),
Tail(w', x), Tail(z', y), AllButLast(w', z').
Теперь мы можем распознавать списки, соответствующие строкам в языке без контекста a ^ nb ^ n:
// ANBN(x) iff x is a list beginning with n 'a's followed by n 'b's
ANBN(()).
ANBN(x) :- Head(y, x), Equal(y, 'a'), Tail(z, x),
Last(w, z), Equal(w, 'b'), AllButLast(z', z),
ANBN(z').
Легко настроить этот предикат, чтобы найти язык палиндромов четной длины, и оттуда легко настроить язык всех палиндромов. Я уверен, что мы также можем принять такие языки, как сбалансированные скобки и т. Д. c. Основываясь на этом опыте, я предполагаю, что мы можем принять все контекстно-свободные языки.
Можем ли мы получить контекстно-зависимый язык? Давайте попробуем ^ nb ^ nc ^ n. Если мы предположим, что DataLog имеет встроенные предикаты, подобные этому, для целочисленных типов:
Zero(x) iff x is equal to zero
Successor(x, y) iff x and y are integers and x = y + 1
Тогда я думаю, что мы можем сделать следующее:
ANBNCN(()).
ANBNCN(x) :- Zero(y), ANBNCNZ(x, y).
ANBNCNZ(x, y) :- BN(x, y).
ANBNCNZ(x, y) :- Head(w, x), Equal(w, 'a'),
Last(z, x), Equal(z, 'c'),
Tail(u, x), AllButLast(v, u),
Successor(r, y), ANBNCNZ(v, r).
BN(x, y) :- Head(w, x), Equal(w, 'b'),
Successor(y, z), Tail(u, x),
BN(u, z).
То, что сказано выше, заключается в следующем:
- пустая строка находится в ^ nb ^ nc ^ n
- в противном случае строка находится в ^ nb ^ nc ^ n, если f (s, 0) истинно
- f (s, n) - true, если s состоит только из n экземпляров 'b'
- f (s, n) - true, если s начинается с a, заканчивается c, и f (s ', n + 1) верно для всего в середине
Это должно работать, так как каждый рекурсивный вызов f (s, n) удаляет один a и один c из заканчивается и помнит, сколько он насчитал. Затем он подсчитывает, что многие случаи b после того, как все a и c исчезли.
Основываясь на этом, я чувствую, что мы, вероятно, можем также использовать некоторые или все контекстно-зависимые языки. Вероятно, отсутствие неограниченного выполнения - это именно то, что отличает линейно-ограниченные автоматы (произведения в грамматиках с фразовой структурой должны иметь RHS не больше, чем LHS) от общих неограниченных грамматик (промежуточные формы которых могут произвольно расти и уменьшаться).