1 votes 1 votes Let $L = \{\text{madeeasy2016}\}$ over $\Sigma = \{m,a,d,e,s,y,2,0,1,6\},$ $L_1=\text{prefix}(L)$ and $L_2= L_1 \Big /{} { \Sigma ^*}$. The number of strings in $L_2$ (assume $L_1$ and $L_2$ do not include empty string) are ______. Theory of Computation theory-of-computation + – saurav04 asked Jan 25, 2016 • edited Jan 27, 2016 by Praveen Saini saurav04 1.9k views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply saurav04 commented Jan 25, 2016 reply Follow Share Given L1=prefix(L) therefore, L1={m,ma,mad,made,madee,madeea,madeeas,madeeasy,madeeasy2,madeeasy20,madeeasy201,madeeasy2016} Now L2=L1/∑* ={ x | xy ∈ L1 for some y∈ ∑* } therefore L2= {a,ad,d,ade,e,de,adee,ee,dee.......} many string but they have given some explanation that L1/∑*=L1 only ....which one is correct? 0 votes 0 votes Riya Roy(Arayana) commented Jan 25, 2016 reply Follow Share 78? 0 votes 0 votes saurav04 commented Jan 25, 2016 reply Follow Share Ans given is just 12 ...what is ur approach? 0 votes 0 votes Riya Roy(Arayana) commented Jan 25, 2016 i edited by Riya Roy(Arayana) Jan 25, 2016 reply Follow Share sorry its 12 only.... You have 13 prefixes right... For those 13 prefixes the language generated in L2 is { m , ma,mad,made ,madee ,madeea ,madeeas, madeeasy, madeeasy2 ,madeeasy20, madeeasy201 ,madeeasy2016} epsilon is not allowed so prefix m is not considered . 0 votes 0 votes saurav04 commented Jan 25, 2016 reply Follow Share Any reason to choose L2=L1/∑*=L1 ,Plz provide some source if possible... 0 votes 0 votes Please log in or register to add a comment.
Best answer 4 votes 4 votes $L =\{\text{madeeasy2016}\}$ $L_1 = \text{prefix}(L)$, excluding empty string $L_1= \{m,ma,mad,made,madee,madeea,madeeas,madeeasy,\\ \qquad \quad madeeasy2,madeeasy20,madeeasy201,madeeasy2016\}$ In general Right Quotient of $L_1$ with $L_2$ means $L_1\Big /L_2=\{x\;:\;xy\in L_1 \;\text{for some}\;y \in L_2\}$ so In our problem $L_2=L_1\Big /\Sigma^*=\{x\;:\;xy\in L_1 \;\text{for some}\;y \in \Sigma^*\}$ for $y=\epsilon$, $L_2=L_1 \Big / \Sigma^* = L_1$ Number of strings in $L_2 =$ Number of strings in $L_1 =12$ Praveen Saini answered Jan 27, 2016 • selected Jan 27, 2016 by saurav04 Praveen Saini comment Share Follow See all 0 reply Please log in or register to add a comment.
2 votes 2 votes Lets explore the quotient operator: L1/L2 = ? ? is every 'x' that satisfies x.y ∈ L1 where y ∈ L2 Now, consider any arbitrary language L. What is L/∑* ? So, take... x.y ∈ L as 'y' can range from epsilon to every string possible, you will find that x is actually a prefix for L. How? Say y='b', and L contains some string like aabbb. So x becomes 'aabb'. So, if you consider all possible x (which is nothing but the quotient) , you will get prefix(L). Now, coming to your question, L1/∑* is nothing but prefix(L1). Thus, L2=Prefix(L1) which inturn is prefix for given string. So, just calculate prefixes, that's it :) Tushar Shinde answered Jan 25, 2016 Tushar Shinde comment Share Follow See all 0 reply Please log in or register to add a comment.