我们假设我们可以访问以下谓词（无论是内置的还是由我们用该语言定义的）：

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,Q1(z).
Q0(x) :- Head(y,'b'),Q2(z).
Q1(x) :- Head(y,Q0(z).
Q1(x) :- Head(y,Q3(z).
Q2(x) :- Head(y,Q0(z).
Q3(x) :- Head(y,Q2(z).
Q3(x) :- Head(y,Q1(z).
EvenAOddB(x) :- Q2(x).

基于此示例，我认为很明显，我们始终可以以这种方式编码转换，因此可以接受任何常规语言。因此，DataLog至少与确定性有限自动机一样强大。

我们可以定义以下内容：

// Last(x,y) iff x is the last element of y
Last(x,y) :- Head(x,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,Head(z,Equal(w,z),Tail(w',Tail(z',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,Last(w,AllButLast(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,Last(z,'c'),Tail(u,AllButLast(v,u),Successor(r,ANBNCNZ(v,r).

BN(x,Successor(y,BN(u,z).

上述内容如下：

• 空字符串在a ^ n b ^ n c ^ n
中
• 否则，如果f（s，0）为true，则字符串在a ^ n b ^ n c ^ n中
如果s仅由n个'b'实例组成，则
• f（s，n）为true
如果s以a开头，以c结尾，并且f（s'，n + 1）对中间的所有事物都成立，则
• f（s，n）为真。

这应该起作用，因为每次递归调用f（s，n）都会在末端去除a和c，并记住已经计数了多少。然后，一旦a和c全部消失，便可以计算出b的许多实例。

基于此，我的感觉是我们也可以使用部分或全部上下文相关的语言。可能，缺乏无界的执行力正是线性有界自动机（短语结构语法的产生的RHS必须不超过LHS）与一般无限制语法（其中间形式可以任意增长和缩小）的区别。 >