I don't understand the value of the following regular expressions.

538 Views Asked by At

$$\begin{align} 0^{*}10^{*} &= \{w ~\mid ~ w \text{ contains a single } 1\} \\ \Sigma^{*}1\Sigma^{*} &= \{w ~\mid ~w \text{ has at least one } 1\} \\ 0 \Sigma^{*}0~\cup ~1\Sigma^{*}1~\cup ~0~\cup ~1 & = \{w ~\mid ~w \text{ starts and ends with the same symbol}\} \end{align}$$

I don't get why in first one says "contains a single 1" and in the second one says "at least one 1" ? Why both can't be "at least one 1" or "conais a single 1" ?

I don't understand the third one at all.

1

There are 1 best solutions below

5
On BEST ANSWER

The only strings that match the regular expression $0^*$ are strings consisting entirely of $0$s. (This includes the empty string.) Thus, a string that matches $0^*1$ must end in a $1$, everything before that $1$ has to match $0^*$, so it must be a string of $0$s (or empty). Finally, a string that matches $0^*10^*$ must start with a string that matches $0^*1$, i.e., zero or more $0$s followed by a single $1$, and then end with a string that matches $0^*$ — a string of $0$s. The possible matches, therefore, are all of the strings of the form $0^m10^n$, where $m$ and $n$ are non-negative integers: $m$ $0$s, a $1$, and $n$ $0$s in that order. And those are precisely the strings that contain exactly one $1$ (and any number of $0$s distributed in any way).

Since $\Sigma=\{0,1\}$, $\Sigma^*$ matches any string of $0$s and $1$s at all (including the empty string. Thus, $\Sigma^*1$ matches any string that ends in a $1$, and $\Sigma^*1\Sigma^*$ matches any string of $0$s and $1$s that has at least one $1$ in it. If you a string $v1w$, where $v$ and $w$ are any strings of $0$s and $1$s, it matches $\Sigma^*1\Sigma^*$, because $v$ matches $\Sigma^*$, $1$ matches $1$, and $w$ matches the second $\Sigma^*$. Thus, $0110$ matches $\Sigma^*1\Sigma^*$: think of it as $(01)(1)(0)$ and match $01$ with $\Sigma^*$, $1$ with $1$, and $0$ with $\Sigma^*$, or as $(0)(1)(10)$ and match $0$ and $10$ with the two $\Sigma^*$s and $1$ with the $1$. It does not match $0^*10^*$, however: after you match the first $0$ with the first $0^*$, you must match the first $1$ with the $1$ of $0^*10^*$, and then the remaining $10$ doesn’t match the final $0^*$ of $0^*10^*$.

To sort out the regular expresseion $0\Sigma^*0\cup 1\Sigma^*1\cup \cup 1$, split it into its four pieces and work out what kinds of strings match them. The pieces are:

  • $0\Sigma^*0$: As we saw above, the $\Sigma^*$ matches any string whatsoever, so any string of the form $0\ldots 0$ will match this regular expression: whatever is between the beginning $0$ and the final $0$ will match $\Sigma^*$.

  • $1\Sigma^*1$: Similarly, this matches any string of the form $1\ldots 1$.

Those two cover all strings with the same first and last symbol except those of length $1$, in which the same symbol is both first and last. Those are covered by the remaining two pieces:

  • $0$: The only string that matches this is $0$, which trivially has the same first and last symbol but is not covered by the first two pieces, because any string that matches either of them must contain at least two symbols.

  • $1$: Similarly, the only string that matches this is $0$, which trivially has the same first and last symbol.