The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+1 vote

asked in Theory of Computation by Junior (637 points) | 71 views

3 Answers

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

answered by Boss (13.2k points)
selected by
0 votes
  • Regular expression are distributive hence option c is right .

answered by Boss (14.3k points)
$(a+b)(a+b)^*$ indeed is equal to $(a+b)^*(a+b)$
Yes . Option 2 is also right
0 votes
Answer is 2
answered by Junior (637 points)

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

36,157 questions
43,608 answers
42,860 users