retagged by
267 views
2 votes
2 votes

Consider the following statements :

  1. Any finite subset of $\{a, b\}^{\ast }$ is a regular language;
  2. For any regular expressions $\mathbf{r}$ and $\mathbf{s}$, the regular expressions $\left(\mathbf{r}^{\ast } \mathbf{s}^{\ast }\right)^{\ast }$ and $(\mathbf{r} \mid \mathbf{s})^{\ast }$ always denote the same language.

Which of the above statements is/are true?

  1. Only $a$
  2. Only $b$
  3. Both
  4. None
retagged by

1 Answer

4 votes
4 votes
$a$ is true because every finite language is regular language.

$b$ is true for every regular expression $r,s.$

Let $R, S$ be any two regular expressions, then :

$$
\begin{aligned}
&(R+S)^{\ast }=\left(R^{\ast }+S^{\ast }\right)^{\ast }=\left(R^{\ast } S^{\ast }\right)^{\ast }=\left(R^{\ast } S\right)^{\ast } R^{\ast }=R^{\ast }\left(S R^{\ast }\right)^{\ast } . \\
&R(S R)^{\ast }=(R S)^{\ast } R .
\end{aligned}
$$
edited by
Answer:

Related questions

2 votes
2 votes
2 answers
1