Engineering

Theory of Computation MCQs: 147 Questions & Answers in Engineering

147 Theory of Computation MCQs in Engineering with answers & explanations. Page 2. Practice objective questions for competitive exams, interviews & self-asse… Use the answer toggle below to show or hide all solutions, tap an option to check one question, or open a question for its own page.

Page 2 of 8

Show answers

Answers hidden — tap an option or use “View Answer” on each question.

Theory of Computation MCQs: 147 Questions & Answers in Engineering

A language is regular if and only if

Which of the following is not a regular expression?

Consider the regular language L = (111+111111)*. The minimum number of states inany DFA accepting this language is

How many strings of length less than 4 contains the language described by the regular expression (x+y)*y(a+ab)*?

Which of the following denotes Chomskianhiearchy?

The concept of FSA is much used in this part of the compiler

The following grammar G = (N, T, P, S)**spaceN = {S, A, B, C, D, E}**spaceT = {a, b, c}**spaceP : S → aAB**spaceAB → CD**spaceCD → CE**spaceC → aC**spaceC → b**spacebE → bc is

The following CFG is in S → aBB**spaceB → bAA**spaceA → a**spaceB → b

Which of the following statements is wrong?

Context free grammar is not closed under

Let the class of language accepted by finite state machine be L1 and the class of languages represented by regular expressions be L2 then

Which of the following statement is wrong?

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

The language accepted by a Push down Automata:

The PDA is called non-deterministic PDA when there are more than one out going edges from……… state:

Let L be a language defined over an alphabet ∑,then the language of strings , defined over ∑, not belonging to L denoted by LC or L. is called :

All NonNull words of the CFL can be generated by the corresponding CFG which is in CNF i.e the grammar in CNF will generate the same language except the:

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?

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

Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

Study tips for Theory of Computation

How many strings of length less than 4 contains the language described by the regular expression (x+y)y(a+ab)?

The following grammar G = (N, T, P, S)spaceN = {S, A, B, C, D, E}spaceT = {a, b, c}spaceP : S → aABspaceAB → CDspaceCD → CEspaceC → aCspaceC → bspacebE → bc is

The following CFG is in S → aBBspaceB → bAAspaceA → a**spaceB → b