652 views

2 Answers

Best answer
4 votes
4 votes

1. False.
If $\lambda$ represents Null string then $R \cup \lambda = R$ is Not always true. It will be true iff $L(R)$ itself contains $\lambda$.

2. True. $RR^* = R(\lambda + R + RR + RRR...) = R + RR + RRR + RRRR + ... = (\lambda + R + RR + RRR...)R = R^*R$

3. True.
We could formally prove it that In Regular expressions, Concatenation is Distributive over Union.

Let's Prove it :

$A.(B + C) = A.B + A.C$  // For typing ease, I am typing $+$ in place of $\cup$ And $A,B,C$ instead of $R1,R2,R3$

First Let's Prove that, If Any String $w$ belongs to $A(B+C)$ then It will also belong to $AB + AC$ i.e. We will prove that $A(B+C)$ is a Subset of $AB + AC$.

If $w$ belongs to $A(B+C)$ then some left part of $w$ must have come from $A$ and remaining right part of $w$ must have come from $B+C$. So, Let me partition $w$ into $xy$ where $x$ has come from $A$ anb $y$ has come from $B+C$..($x$ or $y$ or both could be Null strings as well)
So, $x \in A$ and $y \in (B+C)$..$y$ would have come from either $B$ or $C$ or from both.

So, Now we can see that if $x$ is in $A$ and $y$ is in $B+C$ then $xy$ i.e. $w$ will be definitely in $AB + AC$. Hence, We have so far proven that $A(B+C)$ is a Subset of $AB + AC$.

Similar logic can be used to prove that $AB + AC$ is a Subset of $A(B+C)$ i.e. If any string $s = p.q$ belongs to $AB + AC$ then it will definitely belong to $A(B+C)$. Try it.

4. False.
$R1 \cup (R2 . R3) = (R1 \cup R2).(R1 \cup R3)$.. To prove the Truthness of any formula or theorem, We need to give Formal proof, But to disprove something ---- counter example is enough.

Simplest counter example would be : $R1 = R2 = R3 = a$, So,  $R1 \cup (R2 . R3)$ = $aa + a$ and  $(R1 \cup R2).(R1 \cup R3)$ = $aa$. Hence, $R1 \cup (R2 . R3) = (R1 \cup R2).(R1 \cup R3)$ Not True.

So, We can say that In Regular expressions, Union is NOT Distributive over Concatenation.

selected by

Related questions

0 votes
0 votes
3 answers
1
gateexplore asked Jul 3, 2023
495 views
Which of the following pairs of regular expression are equivalent?(a) 1(01)* and (10)*1(b) x(xx)* and (xx)*x(c) x* and x*x(d) All of the above