The Gateway to Computer Science Excellence
+1 vote

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

in Theory of Computation by Active (1.6k points)
edited by | 534 views

Given L1=prefix(L) therefore,


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?

Ans given is just 12 ...what is ur approach?
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 .

Any reason to choose L2=L1/∑*=L1 ,Plz provide some source if possible...


2 Answers

+4 votes
Best answer

$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$

by Veteran (57k points)
selected by
+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 :) 

by Active (2.2k points)

Related questions

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
50,737 questions
57,300 answers
104,997 users