Какое регулярное выражение требует возврата?

Question

Существует три различных решения для реализации сопоставления регулярных выражений: DFA, NFA и Backtracking. Я ищу примеры:

• регулярное выражение, которое может быть решено с помощью DFA, и причина, почему DFA достаточно.
• регулярное выражение, которое требует NFA и причину, по которой NFA необходим.
• регулярное выражение, требующее возврата и причина, по которой необходим возврат.

Рекомендация для некоторой хорошей литературы по этой теме тоже была бы хороша.

Answer 1

я думаю, что есть более 1 значения для слова возврат - даже '.*a' должен возвращаться, чтобы соответствовать строке "lalaiiiiiii" (потому что .* сначала будет соответствовать всей строке - так что тогда a не будет ничего совпадать - и только тогда он выдаст по одному символу за раз, поэтому окончательное совпадение будет "lala")

Я настоятельно рекомендую http://www.regular -expressions.info /

Answer 2

То, что я узнал до сих пор:

• Каждое регулярное выражение, которое может быть реализовано с помощью NFA, также может быть реализовано с помощью DFA. Каждый NFA может быть преобразован в DFA.

• Регулярные выражения, требующие возврата, являются регулярными выражениями, которые содержат обратные ссылки, такие как /(a)\1/.