retagged by
1,794 views
5 votes
5 votes
Consider languages L1 and L2 over {0,1) alphabet.

L2= {w/w contains some x as a substring and x belongs to L1}

Which of the following must be true?

I. If L1 is regular, L2 is also regular

II. If L1 is CFL, L2 is also CFL

III. If L1 is recursive, L2 is also recursive

(A). I and II only

(B). I, II, III only

(C). I and III only

(D). II and III only
retagged by

3 Answers

0 votes
0 votes

I think answer is Option B. We do not require a seperate automata for deciding L2. All we have to do is the pass the input string to the automata recognizing L1 and if we reach a final state at any point we can stop processing the input string ( even if symbols are remaining in the string as a substring match is sufficient) and decide that it belongs to L2. So whatever is the language of L1 the same holds for L2.

edited by
0 votes
0 votes

1 can not be correct , substring of regular is not always regular

for example L1=0m1n which is regular

a substring of it is 0a1a where a<m,n it is CFL

so looks like D is the answer

III is correct as recursives are closed under complementation!

i do not know how II is correct ,coz lets we  have a cfl=0m1m 0n1n where m<n

now a substring 0m1m0m is substring but it is not CFL..it is CSL

so only III should be correct

edited by

Related questions

3 votes
3 votes
2 answers
3
Shreya Roy asked Nov 18, 2016
1,014 views
Let L = {xy | xwy L1, |x| = |w| = |y|}. Then L is(L1 is regular)(A). Regular(B). Non regular(C). May be regular(D). None
0 votes
0 votes
1 answer
4