0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If you don't want to generate nested brackets, how will you ever describe all regular expressions? $\endgroup$ – reinierpost Jul 14 '17 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 '17 at 7:50
  • $\begingroup$ Did you consider postfix expressions? They are bracket-free. Rather than $S+T$ write $ST+$, etcetera. $\endgroup$ – Hendrik Jan Jul 14 '17 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 '17 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 '17 at 16:10
2
$\begingroup$

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.

$\endgroup$
  • $\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 '17 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 '17 at 17:02
  • $\begingroup$ I might be missing something, but can this expression generate, for example, $0$? $\endgroup$ – Yuval Filmus Jul 14 '17 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 '17 at 1:20

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.