3 ms·
It is proven that Turing machines can recognize a wider class of languages than Chomsky regular expressions. However, the article uses something more powerful t
by ptspts 5y ago
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.
- louhike 5y agoDo you mean Chomsky hierarchy by Chomsky regex?
- nsajko 5y agoRegular languages are an element included in Chomsky's hierarchy: https://en.wikipedia.org/wiki/Chomsky_hierarchy https://en.wikipedia.org/wiki/Chomsky_hierarchy https://en.wikipedia.org/wiki/Formal_language https://en.wikipedia.org/wiki/Formal_language
- deleted 5y ago[deleted]