Theory of Computation

## Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

1. Which of the following a Turing machine does not consist of? a. input tape b. head c. state register d. none of the mentioned Ans- d. none of the mentioned 2. Which of the problems are unsolvable? a. Halting problem b. Boolea…

## Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

1. Which of the following can be used to prove a language is not context free? a. Ardens theorem b. Power Construction method c. Regular Closure d. None of the mentioned Ans- c. Regular Closure 2. The intersection of context fre…

## Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

1. Every Kuroda Normal form grammar generates _____ a. Context free grammar b. Context sensitive grammar c. Unrestricted grammar d. None of the mentioned Ans- b. Context sensitive grammar 2. There is a linear grammar that genera…

## Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

1. Which of the following does not obey pumping lemma for context free languages ? a. Finite languages b. Context free languages c. Unrestricted languages d. None of the mentioned Ans- c. Unrestricted languages 2. What is the pu…

## Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

1. Which of the following does not have left recursions? a. Chomsky Normal Form b. Greibach Normal Form c. Backus Naur Form d. All of the mentioned Ans- b. Greibach Normal Form 2. The format: A->aB refers to which of the foll…

## Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

1. The variable which produces an epsilon is called: a. empty variable b. nullable c. terminal d. all of the mentioned Ans- b. nullable 2. The use of variable dependency graph is in: a. Removal of useless variables b. Removal of…

## Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

1. Find a regular expression for a grammar which generates a language which states : L contains a set of strings starting wth an a and ending with a b, with something in the middle. a. a(a*Ub*)b b. a*(aUb)b* c. a(a*b*)b d. None …

## Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

1. Which of the following relates to Chomsky hierarchy? a. Regular<CFL<CSL<Unrestricted b. CFL<CSL<Unrestricted<Regular c. CSL<Unrestricted<CF<Regular d. None of the mentioned Ans- a. Regular<CFL<…

## Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

1. |-* is the ____ closure of |- a. symmetric and reflexive b. transitive and reflexive c. symmetric and transitive d. none of the mentioned Ans- b. transitive and reflexive 2. A PDA machine configuration (p, w, y) can be correc…

## Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

1. Halting states are of two types. They are: a. Accept and Reject b. Reject and Allow c. Start and Reject d. None of the mentioned Ans- a. Accept and Reject 2. The production of the form A->B , where A and B are non terminals…

## Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

1. Which among the following is not a part of the Context free grammar tuple? a. End symbol b. Start symbol c. Variable d. Production Ans- a. End symbol 2. The following move of a PDA is on the basis of: a. Present state b. Inpu…

## Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

1. Which of the following is a parser for an ambiguous grammar? a. GLR parser b. Chart parser c. All of the mentioned d. None of the mentioned Ans- c. All of the mentioned 2. Which of the following is an real-world programming l…

## Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

1. A DTD is associated with a XML file by means of _____ a. Function b. <!DOCTYPE> c. Macros d. None of the mentioned Ans- b. <!DOCTYPE> 2. Which of them have XML as their default format? a. IWork b. LibreOffice c. O…

## Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

1. The ___ table is created by YACC. a. LALR parsing b. LL parsing c. GLR parsing d. None of the mentioned Ans- a. LALR parsing 2. The YACC takes C code as input and outputs_____ a. Top down parsers b. Bottom up parsers c. Machi…

## Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

1. Which of the following parser reaches the root symbol of the tree at last? a. Top down parser b. Bottom up parser c. TOP down and Bottom up parser d. None of the mentioned Ans- b. Bottom up parser 2. To derive a string using …

## Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

1. A grammar with more than one parse tree is called: a. Unambiguous b. Ambiguous c. Regular d. None of the mentioned Ans- b. Ambiguous 2. The number of leaves in a parse tree with expression E*(E) where * and () are operators a…

## Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

1. Which of the theorem defines the existence of Parikhs theorem? a. Parikh's theorem b. Jacobi theorem c. AF+BG theorem d. None of the mentioned Ans- a. Parikh's theorem 2. Which of the following statements are correct …

## Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

1. Pick the odd one out of the given properties of a regular language: a. Kleene b. Reversal c. Homomorphism d. Membership Ans- d. Membership 2. Which of the following are decision properties? a. Emptiness b. Infiniteness c. Mem…

## Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

1. Which of the following obey the closure properties of Regular language? a. Homomorphism b. Inverse Homomorphism c. Reversal d. All of the mentioned Ans- d. All of the mentioned 2. Which among the following is the closure prop…

## Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

1. Which of the following is/are an example of pigeon hole principle? a. Softball team b. Sock picking c. Hair counting d. All of the mentioned Ans- d. All of the mentioned 2. The language of balanced paranthesis is: a. regular …