Engineering

Theory of Computation MCQs: 147 Questions & Answers in Engineering

147 Theory of Computation MCQs in Engineering with answers & explanations. Practice objective questions for competitive exams, interviews & self-assessment —… 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 1 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

= ∈{ } w has at least as many occurrences of (110)’s as (011)’s}. Let L {w 0,1 * 2 = ∈{ } w has at least as many occurrence of (000)’s as (111)’s}. Which one of the following is TRUE?

A spanning tree for a simple graph of order 24 has

If G is a simple connected 3-regular planar graph where every region is bounded by exactly 3 edges, then the edges of G is

If G is a connected planar graph of v vertices e edges and r regions then

The following grammar G = (N, T, P, S) N = {S, A, B} T = {a, b, c} P : S → aSa S → aAa A → bB B → bB B → c is

A Hamiltonian cycle in a Hamiltonian graph of order 24 has

The following grammar G = (N, T, P, S) N = {S, A, B, C, D, E} T = {a, b, c} P : S → aAB AB → CD CD → CE C → aC C → b bE → bc is

The following grammar G = (N, T, P, S) N = {S, A, B, C} T = {a, b, c} P : S → aS A → bB B → cC C → a is

P, Q, R are three languages. If P & R are regular and if PQ=R, then

Which of the following is true with respect to Kleene’s theorem? 1 A regular language is accepted by a finite automaton. 2 Every language is accepted by a finite automaton or a turingmachine.

Automaton accepting the regular expression of any number of a ' s is:

Grammars that can be translated to DFAs:

Two strings x and y are indistinguishable if:

Given an arbitrary non-deterministic finite automaton NFA with N states, the maximum number of states in an equivalent minimized DFA is at least:

Regular expressions are

The regular expression 0*(10)* denotes the same set as

Consider the NFA M shown below. Let the language accepted by M be L. Let L1 be the language accepted by the NFA M1, obtained by changing the accepting state of M to a non-accepting state and by changing the non-accepting state of M to accepting states. Which of the following statements is true?

Which of the statements is true:

The regular sets are closed under:

Any given transition graph has an equivalent:

Study tips for Theory of Computation

The regular expression 0(10) denotes the same set as