14,853 views
18 votes
18 votes
how to find L1/L2  for some L1 and L2 (is diagram making must )

how to conclude that L1 is divisible or not divisible by L2

1 Answer

Best answer
87 votes
87 votes

no diagram is not neccessary for right quotient (L1/L2) by making differenr strings we can find it

The right quotient of L1 with L2 is the set of all strings x where you can pick some  y from L2 and append it to x to get something from L1. That is, x is in the quotient if there is y in L2 for which xy is in L1.)

Let's agree to write the quotient of L1 by L2 as L1/L2.

Here are some examples:

  1. Say that L1 is the language {fish,dog,carrot} and that  L2 is the language {rot}. Then L1/L2, the quotient of L1 by L2, is the language {car}, because car is the only string for which you can append something from L2 to get something from L1.
  2. Say that L1 is the language {carrot,parrot,rot} and that L2 is the language {rot}. Then L1/L2 is the language {car,par,ϵ}.                                                                          Say that L3= {rot,cheese}  Then L1/L3 is also {car,par,ϵ}
  3. Say that L1={carrot} and L2={t,ot}. Then L1/L2 is {carro,carr}.
  4. Say that L1={xab,yab}and L2={b,ab} Then L1/L2 is {xa,ya,x,y}
  5. Say that L1={ϵ,a,ab,aba,abab,…} and L2={b,bb,bbb, }L2=Then L1/L2 is {a,aba,ababa,…}

  6. In general, if L2 contains ϵ, then L1/L2 will contain L1

  7. In general, if L2=P∪Q, then

    L1/L2=(L1/P)∪(L1/Q).

  8. In general, if L1=P∪Q  then

    L1/L2=(P/L2)∪(Q/L2).

  9. The two foregoing facts mean that you can calculate the right quotient of two languages L 1and L2 as follows: Let s1 be some element of L1 and let s2 be some element of L2. If s2 is a suffix of s1, so that s1=xs2 for some string x, then x is in the quotient L1/L2. Repeat this for every possible choice of s1and s2 and you will have found every element of L1/L2.
selected by

Related questions

5 votes
5 votes
2 answers
1
radha gogia asked Nov 29, 2015
1,498 views
If I take L=a^n b^n and R=(a+b)* so I am getting the value of L/R to be regular ,Am I correct ?
1 votes
1 votes
1 answer
2
Sanjay Sharma asked Apr 27, 2016
879 views
explain with proper procedure is diagram must for such type of questions