2

Let $\Sigma$ be an alphabet, $R$ be the set of regular expressions on $\Sigma$ (that is, trees with leave's values in $\left\{\varepsilon\right\}\cup \Sigma$ and three types of interior nodes, one with arity $1$ and two with arity $2$) and $A$ the set of nondeterministic finite automata with states in $\left\{k\in \Bbb N\mid k \le n\right\}$ for some $n\in \Bbb N$ quotiented by the equivalence relation "are the same up to a permutation of the states".

Let $L_R:R\to \mathcal P\left(\Sigma^*\right)$ be the function that associates to each regular expression the language it recognizes.

Let $L_A:R\to \mathcal P\left(\Sigma^*\right)$ be the function that associates to each nondeterministic finite automaton the language it recognizes.

Is there a bijection $\varphi:R \to A$ so that $L_A\circ \varphi=L_R$, that is, a bijection that "conserves the recognized language"? And if yes, is there an explicit one?

To rephrase the question: Define $\sim_R$ by $\forall x,y\in R, x \sim_R y \iff L_R(x)=L_R(y)$ and $\sim_A$ similarly. By Kleene's theorem, we have $R/\mathord{\sim_R}\cong\left\{L(r)\mid r\in R\right\}=\left\{L(a)\mid a\in A\right\}\cong A/\mathord{\sim_A}$. So my question is equivalent to: Do we have $\forall [r]_R\in R/\mathord{\sim_R},\forall [a]_A\in A/\mathord{\sim_A}, L_R(r)=L_A(a)\implies [r]_R\cong[a]_A$? In other words, are there as many automata as regular expressions that recognize a given regular language?

I tried the usual constructions used to prove Kleene's theorem but for those that are defined as functions (as opposed to those that just give you a method to reduce the size of the problem without telling you where to apply it), I think they all lacked either injectivity (in the $A\to R$ way because those algorithms modified the automaton to give it a special form before applying the main algorithm and so the automaton you had at the beginning and the one you got after putting it in s special form will have the same image) or surjectivity (in the $R\to A$ way since some always use $\varepsilon$ transitions and others never do). This makes me think that $A$ is strictly bigger than $R$ as "language recognizing structure" (no application $A\to R$ preserving the recognized language will be injective) but I have no idea how to prove or disprove this.

Jean Marie
  • 81,803
xavierm02
  • 7,495
  • For any given regular language there is $\aleph_0$ automatons and regular expressions that recognize it, for example if $R$ recognizes $L$, then $R \cup R$ or $R \cap R$ also recognize $L$, similarly with automatons (deterministic or not, you can "expand" first few finite words). For this reason, there exists an bijection, however, I doubt that it is explicit. On the other hand, your elements $[r]_R$ and $[a]_A$ belong to sets that are isomorphic to the set of all regular languages. – dtldarek Aug 21 '13 at 14:47
  • @dtldarek : Thank you :) Since you don't think there is an explicit one, would you know an explicit bijection $X\subset R \to A$ or $R\to X\subset A$ where $X$ has a nice characterization? – xavierm02 Aug 21 '13 at 15:10
  • @dtldarek : And unless someone gets an explicit bijection out of his hat, I'll probably accept an answer similar to yours so you might want to transform you comment into an answer :) – xavierm02 Aug 21 '13 at 15:12
  • I don't know what are you trying to do, but it might be worth looking for canonical representations, e.g. minimal automatons, etc. – dtldarek Aug 21 '13 at 15:26
  • Well for this ( http://math.stackexchange.com/questions/381424/algorithm-for-checking-if-regular-language-has-given-property ), my algorithm may not work because a regular expression can have "redundant" parts. So I thought of getting the minimal DFA associated with the regular expression and then turning it back into a regular expression but then I found out I didn't know how to turn in back into a regular expression in a systematic way and this led to this question. – xavierm02 Aug 21 '13 at 17:09

1 Answers1

1

Transformed from a comment, as requested by the OP.

For any given regular language there is $ℵ_0$ automatons and regular expressions that recognize it, for example if $R$ recognizes $L$, then $R∪R$ or $R∩R$ also recognize $L$, similarly with automatons (deterministic or not, you can "expand" first few finite words). For this reason, there exists an bijection, however, I doubt that it is explicit. On the other hand, your elements $[r]_R$ and $[a]_A$ belong to sets that are isomorphic to the set of all regular languages.

I hope this helps $\ddot\smile$

dtldarek
  • 37,381