Lua 模式可以表示任何常规语言吗？

Question

本题不询问 Lua 模式是否为 PCRE。这个问题已经被问过很多次了，答案肯定是否定的。

相反，我问的是 Lua 模式是否可以通过形式语言定义来类比常规语言。我的直觉是否定的，因为我无法为这种常规语言创建模式：

L = {'foo'}* = {'', 'foo', 'foofoo', 'foofoofoo', ...}

我所有的尝试都失败了，因为 Lua 似乎无法在捕获时使用 Kleene Star：

> print(('foofoo'):find('(foo)*'))
nil

你能证明 Lua 中没有可以表示 L 的模式吗？更一般地说，可以为任何常规语言创建 Lua 模式吗？

Answer 1

Lua 模式不是常规语言。几乎每个 Lua 模式都可以表示为正则语言，但是有很多正则表达式不能表示为 Lua 模式（并且至少有一个 Lua 模式不是正则).而您尝试做的特定常规构造，匹配特定字符序列的重复，使用 Lua 模式是不可能的。一般情况下不会。

基本上，Lua 模式不能做任何需要基于输入流中的多个字符的决策点的事情。普通语言可以。

Answer 2

Kleene Star 可以轻松实施：

function belongs_to_L(str)
   return str:gsub("foo", "") == ""
end

print(belongs_to_L("foofoo"))  --> true
print(belongs_to_L("bar"))     --> false

Can Lua patterns represent any regular language?