News for hackers. Stuff that matters.

A comment on A functioning Turing Machine using Notepad++ and its find/replace regex engine. Parent comment

Re:A functioning Turing Machine using Notepad++ and its find... by ptspts on Tuesday February 22, 2022 @05:56AM (#30426349)
It is proven that Turing machines can recognize a wider class of languages than Chomsky regular expressions. However, the article uses something more powerful than Chomsky regular expressions, because they contain backreferences (as \2 and \4), and also there is a repeated search-and-replace involved, which also adds to their power.
[ Parent | on HN ]
Re:A functioning Turing Machine using Notepad++ and its find... by louhike on Tuesday February 22, 2022 @08:23AM (#30427584)
Do you mean Chomsky hierarchy by Chomsky regex?
[ Parent | on HN ]
Re:A functioning Turing Machine using Notepad++ and its find... by nsajko on Tuesday February 22, 2022 @08:52AM (#30427881)
Regular languages are an element included in Chomsky's hierarchy: https://en.wikipedia.org/wiki/Chomsky_hierarchy https://en.wikipedia.org/wiki/Formal_language
[ Parent | on HN ]