Alphabets = $\{0, 1, \epsilon, \emptyset, [, ], \cup, \circ, \star\}$ where $\circ$ stands for concatenation, $\star$ is kleene star, $\epsilon$ is empty string, $[$ and $]$ are brackets to be used for language to be generated. Only those Regular Expressions to be considered which don't have nested brackets $[[]]$.

How to handle $[ \ ]$ in this problem ? An expression can be - $[1\star\star \cup 0] \cup [\epsilon \cup 1 \circ 0] \cup 1\star$

What would be a regular expression that describes the language of such regular expressions?

Edit -

I want to come up with Regular Expression for the Language of Regular Expressions as show in example above. One thing though is that the regular expression should not generate such expressions which contains nested bracket ( we don't want to consider that ) so $[1 \cup [0 \cup \epsilon]]$ is not valid and should not be generated by the Regular Expression. What I have done and my understanding so far - For single character Regular Expression would be $(0 \cup 1 \cup \epsilon \cup \phi)$. Be reminded that we are creating regular expression for Language of Regular Expressions. So $(0 \cup 1 \cup \epsilon \cup \phi)$ accepts these regular expressions - $0$ , $1$ , $\epsilon$ , $\phi$.

For $0\star\star$ kind of expressions - $(0 \cup 1 \cup \epsilon \cup \phi)\star^{\star}$ should work.

For $0\star\star \cup 1\star$ types we can have $(0 \cup 1 \cup \epsilon \cup \phi)\star^{\star} \bigcup\ (0 \cup 1 \cup \epsilon \cup \phi)\star^{\star}$

I am getting feeling that somewhere I need to use recursion. So I how to handle bracket $[ ]$ in this case ? How to accept those expressions which have brackets and they are not nested ? If anyone can give me logic or direction to solve this problem competely that will also be ok.

  • $\begingroup$ If you don't want to generate nested brackets, how will you ever describe all regular expressions? $\endgroup$ Jul 14, 2017 at 7:16
  • $\begingroup$ A Regular Expression cannot handle nested brackets. Here I have to come up with a regular expression that accepts a language of regular expressions. So you see $[0+1]^{\star}$ is a regular expression that should be generated by the Regular Expression. $\endgroup$
    – Desperado
    Jul 14, 2017 at 7:50
  • $\begingroup$ Did you consider postfix expressions? They are bracket-free. Rather than $S+T$ write $ST+$, etcetera. $\endgroup$ Jul 14, 2017 at 11:20
  • $\begingroup$ This is not about POSTFIX notations. I have to create a Regular Expression, that accepts regular expressions of any form but without nested brackets. $[0+1]^{\star} \cup [01]^{\star}$ is accepted as this does not have nested brackets but $[0+[01]^{\star}]^{\star}$ is not accepted because it has nested brackets. $\endgroup$
    – Desperado
    Jul 14, 2017 at 11:39
  • 1
    $\begingroup$ I have the strong feeling that "regular expressions without nested brackets" are not regular expressions at all, but a properly weaker formalism. $\endgroup$
    – Raphael
    Jul 14, 2017 at 16:10

1 Answer 1


Let us consider first a simpler situation, in which you have only one "atom" $a$, only one binary operator $\circ$, and no unary operator. The expressions you are captured by $$ X (\circ X)^*, \quad X = a+[a(\circ a)^*]. $$ In order to get an actual regular expression, substitute $X$ (surrounded by parentheses) in the left expression.

Adding a postfix operation $\star$ isn't too difficult: $$ Y (\circ Y)^*, \quad Y = A+[A(\circ A)^*]\star^*, \quad A= a\star^*. $$

In order to get an actual regular expression, first substitute $A$ into $Y$, then $Y$ into the leftmost expression.

Finally, the expression you are looking for only differs in that there are several "atoms" and several binary operations: $$ Z (\circ Z)^*, \quad Z = B+[B((\cup + \circ) B)^*]\star^*, \quad B= (0+1+\underline{\epsilon}+\underline{\emptyset})\star^*. $$ Here $\underline{\epsilon},\underline{\emptyset}$ are the versions in your alphabet.

  • $\begingroup$ I must say beautiful and very structured explanation ( solution ) it is. I am still trying to get some bad cases if I will come up with something I ll let you know. $\endgroup$
    – Desperado
    Jul 14, 2017 at 16:42
  • $\begingroup$ Is this solution correct or near correct ? I came up with this one. $(RR\star^{*}(\cup + \circ)RR\star^{*}+[RR\star^{*}(\cup + \circ)RR\star^{*}])((\cup + \circ)(RR\star^{*}(\cup + \circ)RR\star^{*} + [RR\star^{*}(\cup + \circ)RR\star^{*}]))^{*}\ where\ R =(0\cup1\cup\epsilon\cup\phi)$ $\endgroup$
    – Desperado
    Jul 14, 2017 at 17:02
  • $\begingroup$ I might be missing something, but can this expression generate, for example, $0$? $\endgroup$ Jul 14, 2017 at 19:47
  • $\begingroup$ I think yes by converting first $R$ into $0$. Other $R$s can be expanded to $\epsilon$. $\endgroup$
    – Desperado
    Jul 15, 2017 at 1:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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