1 votes 1 votes Let L be a Context Free Language. Even(L) is the set of all strings w in L such that |w| is even. What can you say about Even(L)? (a) It will be regular (b) It will be context-free (c) It is not decidable (d) None of the above Theory of Computation theory-of-computation + – Prateek kumar asked Jan 8, 2017 Prateek kumar 502 views answer comment Share Follow See 1 comment See all 1 1 comment reply Srishty Suman commented Jan 9, 2017 reply Follow Share I think it's B according to what I have concluded. Suppose 'R' is a Regular Language producing even length string & L is a CFL Then, R intersection L will produce CFL of even length string, as the intersection of a Regular Language and a CFL gives CFL. Also. Deciding whether even(L) will produce any string or not is solvable in polynomial time. Hence it is decidable too. Accordingly, answer should be B. Correct me if I am wrong. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Option A) set of all even length strings is regular and can be recognized with a DFA of just two states. Kaushik.P.E answered Jan 8, 2017 Kaushik.P.E comment Share Follow See all 4 Comments See all 4 4 Comments reply Prateek kumar commented Jan 8, 2017 reply Follow Share nop it's not answer 0 votes 0 votes Kaushik.P.E commented Jan 8, 2017 reply Follow Share I think its regular.. whats the answer given? 0 votes 0 votes Pratyush Madhukar commented Jan 8, 2017 reply Follow Share Answer should be A and B. Since the language is regular, it's also context free. 0 votes 0 votes Kaushik.P.E commented Jan 8, 2017 reply Follow Share Isn't that implicit? 0 votes 0 votes Please log in or register to add a comment.
