Können die Lua-Muster eine normale Sprache darstellen?

Question

Diese Frage fragt nicht, ob Lua-Muster PCRE sind. Das wurde mehrmals gefragt und die Antwort ist definitiv nein.

Stattdessen frage ich, ob Lua-Muster eine Analogie zu regulären Sprachen durch die formale Sprachdefinition haben. Mein Instinkt ist nicht, weil ich nicht in der Lage war, ein Muster für diese reguläre Sprache zu erstellen:

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

All meine Versuche fehlgeschlagen, da Lua die Fähigkeit zu fehlen scheint den Kleene Stern auf Captures zu verwenden:

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

Können Sie zeigen, dass es in Lua kein Muster gibt, das L bezeichnen kann, und allgemeiner gesagt, kann ein Lua-Muster für jede reguläre Sprache erstellt werden?

Answer 1

Lua-Muster sind keine regulären Sprachen. Fast jedes Lua-Muster kann als reguläre Sprache ausgedrückt werden, aber es gibt viele reguläre Ausdrücke, die nicht als Lua-Muster (und mindestens ein Lua-Muster, das nicht regelmäßig ist) ausgedrückt werden können. Und das bestimmte reguläre Konstrukt, das Sie versuchen, Wiederholungen einer bestimmten Zeichenfolge zu finden, ist mit Lua-Mustern nicht möglich. Nicht im allgemeinen Fall.

Grundsätzlich können Lua-Muster nichts tun, was Entscheidungspunkte erfordern würde, die auf mehr als einem Zeichen im Eingabestrom basieren. Reguläre Sprachen können.

Answer 2

Kleene Stern leicht umgesetzt werden können:

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

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