Могут ли шаблоны Lua представлять любой обычный язык?

Question

Этот вопрос не спрашивает, являются ли шаблоны Lua PCRE. Это было задано несколько раз, и ответ определенно нет.

Вместо этого, я спрашиваю, имеют ли образцы Lua аналогию с обычными языками посредством формального определения языка. не мой инстинкт не потому, что я не был в состоянии создать шаблон для этого регулярного языка:

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

Все мои попытки не удалось, потому что Lua по-видимому, не имеют возможности использовать Клини Звезда на захватах:

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

Можете ли вы показать, что в Lua нет шаблона, который может обозначать L, и, в общем, можно ли создать шаблон Lua для любого обычного языка?

Answer 1

Модели Lua не являются обычными языками. Почти каждый шаблон Lua может быть выражен как обычный язык, но существует множество регулярных выражений, которые не могут быть выражены как шаблон Lua (и, по крайней мере, один шаблон Lua, который не является регулярным). И конкретная регулярная конструкция, которую вы пытаетесь сделать, соответствует повторениям определенной последовательности символов, невозможна с шаблонами Lua. Не в общем случае.

В принципе, шаблоны Lua не могут делать ничего, что требовало бы точек принятия решений на основе более чем одного символа во входном потоке. Регулярные языки могут.

Answer 2

Клини Звезда может быть легко реализован:

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

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