search
Log In
1 vote
842 views

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
edited by
842 views
0

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

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$


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 :) 

Related questions

1 vote
0 answers
1
160 views
It is undecidable whether the complement of a CFL is also a CFL. Exercise $9.5.2$ can be used to show it is undecidable whether the complement of a CFL is regular, but that is not the same thing. To prove our initial claim, we need to define a different language that ... $7.2.5(b)$.
asked Jul 26, 2019 in Theory of Computation Lakshman Patel RJIT 160 views
0 votes
0 answers
2
95 views
Show that the language $\overline{L_A}\cup \overline{L_B}$ is a regular language if and only if it is the set of all strings over its alphabet;i.e., if and only if the instance $(A,B)$ of PCP has no solution. Thus, prove that it is ... closed under inverse homomorphism, complementation and the pumping lemma for regular sets to show that $\overline{L_A}\cup \overline{L_B}$ is not regular.
asked Jul 26, 2019 in Theory of Computation Lakshman Patel RJIT 95 views
0 votes
0 answers
3
60 views
Let $L$ be the set of (codes for) context-free grammars $G$ such that $L(G)$ contains at least one palindrome. Show that $L$ is undecidable. Hint: Reduce PCP to $L$ by constructing, from each instance of PCP a grammar whose language contains a palindrome if and only if the PCP instance has a solution.
asked Jul 26, 2019 in Theory of Computation Lakshman Patel RJIT 60 views
0 votes
0 answers
4
125 views
A Post tag system consists of a set of pairs of strings chosen from some finite alphabet $\Sigma$ and a start string. If $(w,x)$ is a pair, and $y$ is any string over $\Sigma$, we say that $wy\vdash yx$ ... by one move of $M$. If $M$ enters an accepting state, arrange that the current strings can eventually be erased, i.e., reduced to $\epsilon$.
asked Jul 21, 2019 in Theory of Computation Lakshman Patel RJIT 125 views
...