假设我们可以访问以下谓词，无论是内置的还是由我们用该语言定义的：
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首先，我认为很明显，该语言可以接受所有常规语言。根据Myhill-Nerode定理，对于正常语言，最小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至少与确定性有限自动机一样强大。
我们可以定义这个：
// 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 ^ n b ^ 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').很容易调整谓词以找到偶数回文的语言，从那里很容易进行调整以找到所有回文的语言。我相信我们也可以接受平衡括号等语言，基于这种经验，我猜想我们可以接受所有上下文无关的语言。
我们可以使用上下文相关的语言吗？让我们尝试a ^ n b ^ n c ^ 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).上面说的是以下内容：
这应该起作用，因为每次递归调用f（s，n）都会在末端去除a a和one c并记住已经计数了多少。然后，一旦所有a和c都消失了，它就会计算出b的许多实例。
基于此，我的感觉是我们也可以使用部分或全部上下文相关的语言。可能，缺乏无界的执行力正是线性有界自动机（短语结构语法的产生的RHS必须不超过LHS）与一般无限制语法（其中间形式可以任意增长和缩小）的区别。