Operations without common elements can not be generated using a finite state automata I heard that some operations involving regexes that do not have common elements can NOT be generated using a finite automata. I do not remember what it was, where it was from, can anyone tell me what that could possibly be?
Edit : I finally managed to find the exact statement. Here it is, below :
A language (like $(00)^n (11)^n$) can not be generated by an FSM since there is no common character in &quot;00&quot; and &quot;11&quot;. We need to keep count of both which is not possible with a finite automata as the count can be infinite.
One has to differentiate between regex in computer science and regex in real world programming languages. In compsci regular expressions are defined to only recognize regular languages, which are the same languages DFAs can recognize, thereby making DFAs and regex a descriptions of the same class of languages.
In real world application the recognition of regular languages is somewhat limiting which is the reason why many regex libraries introduce operators which allow you to recognize languages that are not regular. One such operator is recursion (?R) see here for an example using python. Notice that the language in the article is the balanced parentheses language which is a well known context free language that is not regular and thus can not be recognized by a DFA.