How to determine if a word in $\Sigma^*$ is in a language?

Question

I'm currently doing work on discrete mathematics in my free time and am having some difficulties with understanding some questions pertaining to Languages defined by regular expressions. To be specific, I'm stuck on the following practice question:

For $\Sigma=\{0,1\}$, determine whether the word $00010$ in $\Sigma^*$ is in each of the languages below. Explain.

• $\{00\}\{0\}^*\{10\}$
• $\{000\}^*\{1\}^*\{0\}$
• $\{00\}^*\{10\}^*$

I'm a bit stuck on understanding how to calculate these three languages. Do I just multiply/concatenate them together step by step? How would I go about doing that? Any help is appreciated. Thanks!

Answer 1

The first language, $\{00\}\{0\}^*\{10\}$, consists of all words in $\Sigma^*$ that begin with $00$, end with $10$, and have any number of zeroes (including none at all) between those two segments. You could describe them as the words of the form $000^n10$, where $n\ge 0$, and $x^n$ means a string of $n$ $x$s. Alternatively, you could combine the two required zeroes with the optional ones and describe the language as the words of the form $0^n10$, where $n\ge 2$. Is $00010$ of this form? Yes, with $n=3$.

Now let’s look at the second language, $\{000\}^*\{1\}^*\{0\}$. The expression $\{000\}^*$ corresponds to taking any finite number of copies of $000$, including none at all, and concatenating them: $\lambda$, $000$, $000000$, $000000000$, and so on (where $\lambda$ stands for the empty word). Using the same kind of notation as in the first paragraph, we can say that it corresponds to the words of the form $(000)^{3n}$ for $n\ge 0$. The $\{1\}^*$ gives any non-negative number of ones, so it gives us all words of the form $1^m$ for $m\ge 0$. Thus, the language consists of all words of the form $(000)^{3n}1^m0$ with $n,m\ge 0$. Is it possible to choose $n$ and $m$ so that $00010$ has this form? Sure: take $n=m=1$.

I’ll leave the last one for you to try, now that you’ve seen a way of attacking the problem.