1
$\begingroup$

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 "00" and "11". We need to keep count of both which is not possible with a finite automata as the count can be infinite.

Improve this question
$\endgroup$
  • $\begingroup$ What do you mean by "regexes that do not have common elements"? Or "operations involving" such regexes? Can you be more specific? $\endgroup$ – D.W.♦ Oct 15 '20 at 5:13
  • $\begingroup$ @D.W. I managed to find the exact statement. It is from an online site and the answer is from a site tutor, or whatever that is called. I was not able to find the statement. $\endgroup$ – oldsailorpopoye Oct 15 '20 at 5:38
  • $\begingroup$ I'm a bit confused $(00)^n(11)^n$ can neither be recognized by regex or by DFA (if you use the usual definitions for regex). Also $(10)^n(11)^n$ can't be recognized (by DFA/regex) despite there being common elements - the counting aspect of the statement is much more decisive. Anyhow is your question resolved? $\endgroup$ – plshelp Oct 15 '20 at 5:51
  • $\begingroup$ It isn't. I do not understand the statement in italics. I need an explanation for why that (statement, and not the example language) is true in general. $\endgroup$ – oldsailorpopoye Oct 15 '20 at 5:53
  • $\begingroup$ I think it's better to ask the tutor about this rather cryptic remark. $\endgroup$ – Yuval Filmus Oct 15 '20 at 5:59
1
$\begingroup$

The remark by the tutor is very poorly worded. My best guess is that it refers to the following situation. Let $L_{x,y}$ be the set of all words that have as many copies of $x$ as that of $y$. Then $L_{0,1}$ is not regular, but $L_{01,10}$ is regular, since it equals $(0^+1^+)^*0^+ + (1^+0^+)^*1^+ + \epsilon$.

Improve this answer
$\endgroup$
  • $\begingroup$ which according to him probably means that $L_{x,y}$ is regular $\implies$ $x \cap y \neq \phi$ (not necessarily vice versa). Does that hold true in general for an infinite language? $\endgroup$ – oldsailorpopoye Oct 15 '20 at 6:34
  • $\begingroup$ I’m not sure what you mean by infinite language. $\endgroup$ – Yuval Filmus Oct 15 '20 at 8:19
  • $\begingroup$ A language that generates words having length $\geq \text{N}$ for every $\text{N} \in \mathbb{N}$. One that can make use of the pumping lemma. $\endgroup$ – oldsailorpopoye Oct 15 '20 at 8:30
  • $\begingroup$ I still don’t understand your question. $\endgroup$ – Yuval Filmus Oct 15 '20 at 8:32
  • $\begingroup$ Conjecture : Denote by $L_{x,y}$ the set of all words that have as many copies of $x$ as that of $y$. Then if $L_{x,y}$ is regular, $x \cap y \neq \phi$. Is this conjecture true? There is something that I often see that FSA have constant memory, and this seems to violate that criteria. I am not sure what that means exactly, I have seen it. $\endgroup$ – oldsailorpopoye Oct 15 '20 at 8:39
1
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ I appreciate your answer. I have edited the question. $\endgroup$ – oldsailorpopoye Oct 15 '20 at 5:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.