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…