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

Ans. D

in Theory of Computation by Loyal (6.7k points) | 136 views
0
Please discuss the approach for this question
0
L(r1) = {0,01,011,0111......} , L(r2) = {1,01,001,0001......}

in question it is giving that L is any regular language obtained with quotient of L(r1) and L(r2)

then if you will consider right quotient ,

L = L(r1)/L(r2) = {$\epsilon$, 0,01,011,....} = $(01^{*})^{*}$

f you will consider left quotient ,

L = L(r1)\L(r2) = {$\epsilon$, 1,01,001,....} = $(0^{*}1)^{*}$

clearly answer is D)none.
0
Can you explain how u did  L(r1)/L(r2) ??? Please
0
by default, Regular Language follow left/right quotient???
0
Are you asking about that regular languages are closed under left/right quotient?
0
yes, left/right or both??
0
yes regular languages are closed. but not closed under cfl.

1 Answer

+1 vote
Best answer

L(r1) = {0,01,011,0111......} , L(r2) = {1,01,001,0001......}

in question it is giving that L is any regular language obtained with quotient of L(r1) and L(r2)

then if you will consider right quotient ,

L = L(r1)/L(r2) = {0,01,011,0111.....}/{1,01,001,0001......} 

now in L only those string will come which follow below property,

L_1 / L_2 = \{w \ |  \ \exists x ((x \in L_2)  \land (wx \in L_1)) \}(from wikipedia)

means there is one x in L2 by which you can drive wx in L1.

-> Now in L2 first string is 1 and in L1 you can drive 0(from the string 01(w=0,x=1)), 01(from the string 011(w=01,x=1)),  011(from the string 0111(w=011,x=1))like wise go further...

-> Now in L2 second string is 01 and in L1 you can drive only $\epsilon$(from the string 01(w=$\epsilon$,x=01)) nothing else.

-> after second string in L2 third is 001. Now you can not drive any string from this. Same for others also

 

So finally L will contain strings like-

={$\epsilon$, 0,01,011,....} = $(\epsilon + 01^{*})$

-----------------------------------------------------------------------------

if you will consider left quotient ,

L = L(r1)\L(r2) = {0,01,011,0111.....}\{1,01,001,0001......} 

= {$\epsilon$, 1,01,001,....} = $(\epsilon + 0^{*}1)$

now in L only those string will come which follow below property,

L_1 \backslash L_2 = \{w \ | \ \exists x ((x \in L_1)  \land (xw \in L_2))\}

clearly answer is D)none.

For better understanding - https://math.stackexchange.com/questions/871662/finding-right-quotient-of-languages

by Loyal (8.9k points)
edited by
+1

i think it will be $\left ( \epsilon + 01^{*} \right )$ instead of $\left ( 01^{*} \right )^{*}$

Related questions

+2 votes
4 answers
4
+1 vote
0 answers
5
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
49,830 questions
54,807 answers
189,530 comments
80,836 users