1
$\begingroup$

Does $(0 + 10^{*}1)^{*}$ simplify to the following language: Set of all binary strings with even number of ones. In specific, does the * inside the brackets get evaluated first or the outer * gets evaluated first. Or does it even matter while simplifying as what we finally need is the set of all strings possible with this expression?

$\endgroup$
  • 1
    $\begingroup$ I'm not sure what you mean by "get evaluated first". $\endgroup$ – David Richerby Feb 16 '16 at 5:55
  • 1
    $\begingroup$ Not sure in which sense you mean this is a "simplification". $\endgroup$ – Raphael Feb 16 '16 at 11:50
  • 1
    $\begingroup$ Anyway, what have you tried? Where did you get stuck? You claim that the given regular expression generates a specific language, so try an prove your claim! $\endgroup$ – Raphael Feb 16 '16 at 11:51
2
$\begingroup$

One way to go about this is to show that $S=T$, where

$S = $ the set of all strings over $\{0,1\}$ containing an even number of 1s,

$T = $ the set of all strings which can be represented by the regexp $(0+10^*1)^*$

Showing that $S\subseteq T$ can be done by induction on the number of 1's in a string and showing that $T\subseteq S$ is even easier.

$\endgroup$
2
$\begingroup$

(This is not a question on formally proving the meaning of expressions and their equivalence, but on how to read them.)

I see your point: if you match an expression with a string then the outer $*$ fixes the number of pairs of $1$'s, and the inner $*$ determines the number of $0$'s in between each of these pairs. That suggests outside in.

Technically the meaning ("evaluation") of $10^*1$ however is not choosing a single string, but the full language of any number of $0$'s between two $1$'s. Then (once the inside language is evaluated) we concatenate arbitrary sequences of elements in the string. That definitely is inside-out.

Compare this with another example. The expression $(0+1)^*$ has the same source of confusion. It is not: I choose either $0$ or $1$, and then repeat that letter, but I repeat the choice $0$ or $1$ while concatenating. That seems outside-in, however the evaluation of $(0+1)$ is not a single letter, but of the set $\{0,1\}$. Then the star evaluates that to $\{0,1\}^*$, the set of all strings over $\{0,1\}$.

$\endgroup$
2
$\begingroup$

Yes, $(0+10^*1)^∗$ denotes the set of all binary strings with even number of ones. Or more technically $L(\ (0+10^*1)^∗ \ ) = \{ w \ |\ w$ is a binary string containing even number of 1's $\}$. We denote language of a regular expression $E$ as $L(E)$.

To understand regular expressions, you need to understand the recursive definition of regular expressions.

if $E$ and $F$ are regular expressions $E$+$F$ is regular expression.
if $E$ and $F$ are regular expressions $EF$ is regular expression.
if $E$ is regular expression $E^*$ is regular expression.
For basis, $\epsilon$ and symbols from alphabet $\Sigma$ are also regular expressions.

Next language of regular expressions for each of the above operations is defined: union, concatenation and repetition, respectively. For basis, it is sets of empty string or a single symbol, as the case may be.

Now if $w \in L(E)$ then $L(E^*)$ is not just $wwwww...$, it is also any $w_1w_2w_3...$ (0 or more times) such that $w_1 \in L(E)$, $w_2 \in L(E)$, $w_3 \in L(E)$, etc.

So $(0+10^*1)^*$ is really $(0+10^*1)(0+10^*1)(0+10^*1)...$ (0 or more times). Thus, you work with the outer $*$ operator first and then work with the inner $*$ operator.

Next comes the question of simplification. Either you want to describe the language of a regular expression in most simplest manner possible, or you want to describe the most simple regular expression for a given language. Both these are hard to do. Even if you are given a minimum DFA of the language, to compute minimum regular expression for it is NP-complete (the decision version: does there exist a regular expression of less than $k$ length for the given DFA).

We can minimize DFA but unfortunately we do not have efficient algorithms to minimize NFA or regular expressions unless $P = PSPACE$. See Minimizing NFA’s and Regular Expressions Gregor Gramlich and Georg Schnitger.

However $(0+10^*1)^*$ is set of all binary strings with even number of ones. Yet another expressions are $0^*(10^*10^*)^*$, $(0^*10^*1)^*0^*$, $(0^*10^*10^*)^*$ and so on. The outline of proof that the regular expression $(0+10^*1)^*$ is indeed the language mentioned above is as follows: enter image description here

First we draw a DFA for the language. If we eliminate the state $q_1$ we get the equivalent (enhanced) DFA in the right. It is easy to see that the equivalent regular expression is same. This is kind of reverse-engineering.

Sometimes it is easy to go this way, rather than finding the language of regular expression by automated procedures. Sometimes we can use regular expression algebra also to analyze and simplify regular expressions.

$\endgroup$
  • 2
    $\begingroup$ I disagree that the question should be answered in its current form. That said, the OP asks "is this correct?" and I think any answer should provide at least the sketch of a proof -- why should the OP believe your (or anybody's) verdict any more than their own? $\endgroup$ – Raphael Feb 16 '16 at 15:09
  • $\begingroup$ Fine, here it is, a simple enough proof outline. $\endgroup$ – Shreesh Feb 16 '16 at 15:55

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.