The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+2 votes

Best answer

**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.

0 votes

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.5k
- Digital Logic 2.1k
- Programming & DS 4k
- Algorithms 3.4k
- Theory of Computation 4.2k
- Compiler Design 1.6k
- Databases 3.1k
- CO & Architecture 2.7k
- Computer Networks 3.1k
- Non GATE 1.1k
- Others 1.4k
- Admissions 501
- Exam Queries 450
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

38,106 questions

45,610 answers

132,250 comments

49,239 users