- Option : D
- Explanation :

Is the language represented by regular expression

L(G) is the language generated by context free grammar

L(M) is the language accepted by Turing Machine

I. The problem a given regular expression R and a string w, is is a membership problem. Membership problem is decidable for Finite state machine and regular expression.

II. Given Context free grammar G, is L(G) is ϕ?, is emptiness problem for context free grammar. Emptiness problem is decidable for CFG by checking usefulness of start symbol.

III. A given context free grammar G, is L(G) is Σ* for some alphabet Σ?, is undecidable problem. We can’t check whether L(G) = Σ* or not but rather we can check complement of L(G) is ϕ. Since context free language are not closed under complement operation L(G) may be language accepted by Turing Machine and we can’t check emptiness for Turing machine.

IV. Given a Turing Machine M and a string w, is w Î L(M)?, is a membership problem for TM. Membership problem is not a decidable problem for TM.

You must be logged in to post a comment.

- Option : A
- Explanation :

Number of blocks of main memory = 2^{32}/ 2^{5}= 2^{27}

Number of blocks in cache memory = 512 = 2^{9}

1 Cache block points to 2^{27}/ 2^{9}= 2^{18}lines

So, Number of TAG bits required = 18 bits.

You must be logged in to post a comment.

You must be logged in to post a comment.

- Option : D
- Explanation :

L_{1}is neither regular nor context free but context sensitive language.

L_{2}is context free, push any number of a’s and then for each b, pop two c’s until all b’s are over and this can be done by using only one stack.

L_{3}is not context free because we are not sure when to pop b and push a, because it is comparison between three consecutive terminals.

Clearly L_{3}is deterministic context free because we are sure of pushing a into stack first and on seeing b we are sure of popping a.

Statement III and IV are correct, option (D) is true.

You must be logged in to post a comment.

You must be logged in to post a comment.

You must be logged in to post a comment.