Question

Let $x,y$ and $z$ be regular expressions. Let $\alpha ,\beta ,\Gamma$ be regular expressions defined as follows.
$\alpha =(x\ast y)\ast x\ast y\beta =x\ast y(x\ast y)\ast \Gamma =x\ast (yx\ast )\ast y$

Let L$\left(\alpha \right)$, L$\left(\beta \right)$, L$\left(\Gamma \right)$ be language generated by regular expressions $\alpha ,\beta ,\Gamma$ respectively. Which of the following is true?

• A. $L\left(\alpha \right)\subset L\left(\beta \right),L\left(\beta \right)\subset L\left(\Gamma \right)$
• B. $L\left(\beta \right)\subset L\left(\alpha \right),L\left(\beta \right)\subset L\left(\Gamma \right)$
• C. $L\left(\alpha \right)=L\left(\beta \right),L\left(\beta \right)=L\left(\Gamma \right)$
• D. $L\left(\alpha \right)\ne L\left(\Gamma \right),L\left(\beta \right)\ne L\left(\Gamma \right)$

Answer 1

The correct option is C $L\left(\alpha \right)=L\left(\beta \right),L\left(\beta \right)=L\left(\Gamma \right)$

$\begin{array}{cc}\Gamma & =x\ast (yx\ast )\ast y\\ \text{Take}P& =x\ast ,Q=y\\ \text{Now use}P\left(QP\right)\ast & =\left(PQ\right)\ast P\text{to get}\alpha =(x\ast y)\ast x\ast y\\ \text{Now take}P& =y.Q=x\ast \\ \text{And use}\left(PQ\right)\ast P& =P\left(QP\right)\ast \text{to get}\beta =x\ast y(x\ast y)\ast \end{array}$
$\text{Since we are able to derive}\alpha \text{and}\beta \text{from}\Gamma \text{, option (d) is correct. (All are equal)}$