Theory of Computation Practice Test | Practice Test / Quiz / MCQs

Classes | Practice Tests / Quizzes | User Guide | Life Manuals

28.5K quizzes covering K–12, CBSE, SAT, ACT, GRE, UPSC, SSC, Banking, Reasoning & more.

General Studies (Hindi)
| Take A Quiz

Home > General Studies (Hindi) > Quizzes > Theory of Computation Practice Test

Theory of Computation Practice Test

Fast practice, instant feedback. Timer auto-submits when time’s up.

Avg score: 71% • Most missed: “If PCP is decidable then MPCP is”

In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how efficiently they can be solved or to what degree (e.g., approximate solutions versus precise ones). The field is divided into three major branches: automata theory and formal languages, computability theory, and computational complexity theory, which are linked by the question: "What are the fundamental capabilities and limitations of computers?" (Source: Wikipedia) The 'theory of computation' is important... Show more

In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how efficiently they can be solved or to what degree (e.g., approximate solutions versus precise ones).

The field is divided into three major branches: automata theory and formal languages, computability theory, and computational complexity theory, which are linked by the question: "What are the fundamental capabilities and limitations of computers?"

(Source: Wikipedia)

The 'theory of computation' is important in computing because it forms the basis for:
1. Writing efficient algorithms that run in computing devices.
2. Programming language research and their development.
3. Efficient compiler design and construction

Show less

Theory of Computation Practice Test

Time left 00:00

1. The set that can be recognized by a deterministic finite state automaton is

1, 2, 4, 8……2n ….. written in unary1, 2, 4, 8……2n ….. written in binaryThe set {1, 101, 11011, 1110111, …….}The set of binary string in which the number of 0’s is same as the number of1’s

2. Consider a language L for which there exists a Turing machine ™, T, that accepts every word in L and either rejects or loops for every word that is not in L. The language L is

NP hardRecursively enumerableRecursiveNP complete

3. 3-SAT and 2-SAT problems are

Undecidable and NP-completeBoth NP-completeBoth in PNP-complete and in P respectively

4. Let L be any infinite regular language, defined over an alphabet Σ then there exist three strings x, y and z belonging to Σ such that all the strings of the form XY^ n Z for n=1,2,3, … are the words in L called

Complement of LPumping LemmaNone in givenKleene’s theorem

5. Match all items in Group 1 with correct options from those given in Group 2. List I List II**spaceP. Regular Expression 1. Syntax analysis**spaceQ. Push down automata 2. Code Generation**spaceR. Dataflow analysis 3. Lexical analysis**spaceS. Register allocation 4. Code optimization

P-2, Q-1, R-4, S-3P-3, Q-1, R-4, S-2P-4, Q-1, R-2, S-3P-3, Q-4, R-1, S-2

6. Give a production grammar for the language L = {x/x ∈ (a,b)*, the number of a’s in x is multiple of 3}.

None of these{S->bS,S->b,S->aA,S->bA,A->aB,B->bB,B->aS,S->a}{S->aS,S->bA,A->bB,B->bBa,B->bB}{S->aaS,S->bbA,A->bB,B->ba}

7. Consider the following Finite State Automaton The language accepted by this automaton is given by the regular expression

b*a(a+b)*b*ab*ab*ab(a+b)*b*ab*ab

8. Consider the following statements
I. Recursive languages are closed under complementation
II. Recursively enumerable languages are closed under union
III. Recursively enumerable languages are closed under complementation
Which of the above statement are TRUE?

I and IIII onlyI and IIII and III

9. Choose the correct statement

recursive set ⊆ recursive enumerable settotal function is same as partial functionrecursive sets are analogous to total functionsboth recursive set ⊆ recursive enumerable set and recursive sets are analogous to total functions are correct.

10. Recursively enumerable languages are not closed under:

UnionConcatenationComplementationIntersection

11. Let L={w (0 + 1)* w has even number of 1s}, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expression below represents L?

0*(10*10*)*0*(10*1*)*0*(0*10*1)*0*1(10*1)*10*

12. Which one of the following is the strongest correct statement about a finite language Lover a finite alphabet Σ?

L is recursiveL is undecidableL is a regular setL is a CSL

13. Which of the following instances of the post correspondence problem has a viable sequence (a solution)?

{(ab, aba), (baa, aa), (aba, baa)}None of these{(ab, abb), (ba, aaa), (aa, a)}{(b, bb), (bb, bab), (bab, abb), (abb, babb)}

14. PCP is:

Sometimes DecidableDecidableUndecidableNone of the

15. Grammar that produce more than one Parse tree for same sentence is:

AmbiguousUnambiguousComplementationConcatenation

16. Context free grammar is not closed under

Complementationkleene starUnionProduct operation

17. If PCP is decidable then MPCP is

None of theUndecidableCan’t SayDecidable

18. Which of the following assertions about Turing Machines is true? Blank symbol(s) may occur in the input. At any stage of a computation, there are only finitely many non-blank Symbols on the tape.

Assertions ( a) and ( b) are both true.Neither ( a) nor ( b) is true.None of aboveBoth False

19. Left hand side of a production in CFG consists of:

One non-terminalOne terminalTerminals and non-terminalsMore than one terminal

20. A pushdown automata behaves like a Turing machine, when it has number of auxiliary/ memory.

both exactly 2 or more are correct2 or more0exactly 2

21. Which of the following problem is undecidable?

Membership problem for CSLMembership problem for regular setsMembership problem for type 0 languagesMembership problem for CFL

22. A universal Turing machine is a

reprogrammable truing machinesingle tape Turing machinenone of themtwo-tape Turing machine

23. Which one of the following is true regarding FOTRAN?

It is a context sensitive languageIt is a context free languageIt is a regular languageNone of these

24. If a language is denoted by a regular expression L = ( x )* (x y x ), then which of the following is not a legal string within L ?

xxyxxyxyxyx

25. Let FHAM be the problem of finding a Hamiltonian cycle in a graph G and DHAM be the problem of determining if a Hamiltonial cycle exists in a graph. Which one of the following is TRUE?

DHAM is NP hard, but FHAM is notNeither FHAM nor DHAM is NP hardBoth FHAM and DHAM are NP-hardFHAM is NP hard, but DHAM is not

Welcome to Fatskills

Join 4M+ learners. Unlock unlimited quizzes, wrong-answer tracking, flashcards + reminders, study guides, and 1-on-1 challenges.

Create a free account Sign in

900+ exams • Millions of questions • No spam

❤ If you liked Fatskills, consider supporting us by checking out The Life Manuals You Never Got.

🌈 Our mission is to help improve your scores in any subject and exam withonline quizzes, practice tests, study guides, & advice for students. Since 2018.

About | Explore | User Guide | Topics | Subjects | Doubt Solver | Career Aptitude Test | Answers | Free Tools | What Should We Know?
Privacy | Terms |

All trademarks, logos and brand names are the property of their respective owners. All company, product and service names used in this website are for identification purposes only. Use of these names, trademarks and brands does not imply endorsement.

25 Questions

❤ If you liked Fatskills, consider supporting us by checking out The Life Manuals You Never Got.

About | Explore | User Guide | Topics | Subjects | Doubt Solver | Career Aptitude Test | Answers | Free Tools | What Should We Know?
Privacy | Terms |

Without work one finishes nothing. - Ralph Waldo Emerson
© 2026 Fatskills.com

All trademarks, logos and brand names are the property of their respective owners. All company, product and service names used in this website are for identification purposes only. Use of these names, trademarks and brands does not imply endorsement.

25 Questions

❤ If you liked Fatskills, consider supporting us by checking out The Life Manuals You Never Got.

About | Explore | User Guide | Topics | Subjects | Doubt Solver | Career Aptitude Test | Answers | Free Tools | What Should We Know? Privacy | Terms |

Without work one finishes nothing. - Ralph Waldo Emerson© 2026 Fatskills.com

All trademarks, logos and brand names are the property of their respective owners. All company, product and service names used in this website are for identification purposes only. Use of these names, trademarks and brands does not imply endorsement.

About | Explore | User Guide | Topics | Subjects | Doubt Solver | Career Aptitude Test | Answers | Free Tools | What Should We Know?
Privacy | Terms |

Without work one finishes nothing. - Ralph Waldo Emerson
© 2026 Fatskills.com