adplus-dvertising

Welcome to the Theory of Computation(TOC) MCQs Page

Dive deep into the fascinating world of Theory of Computation(TOC) with our comprehensive set of Multiple-Choice Questions (MCQs). This page is dedicated to exploring the fundamental concepts and intricacies of Theory of Computation(TOC), a crucial aspect of UGC CBSE NET Exam. In this section, you will encounter a diverse range of MCQs that cover various aspects of Theory of Computation(TOC), from the basic principles to advanced topics. Each question is thoughtfully crafted to challenge your knowledge and deepen your understanding of this critical subcategory within UGC CBSE NET Exam.

frame-decoration

Check out the MCQs below to embark on an enriching journey through Theory of Computation(TOC). Test your knowledge, expand your horizons, and solidify your grasp on this vital area of UGC CBSE NET Exam.

Note: Each MCQ comes with multiple answer choices. Select the most appropriate option and test your understanding of Theory of Computation(TOC). You can click on an option to test your knowledge before viewing the solution for a MCQ. Happy learning!

Theory of Computation(TOC) MCQs | Page 2 of 16

Explore more Topics under UGC CBSE NET Exam

Q11.
Given the following statements:

S1: If L is a regular language then the language {uv | u ∈  L, v ∈ LR } is also regular.
S2: L = {wwR} is regular language.

Which of the following is true?

a.

S1 is not correct and S2 is not correct

b.

S1 is not correct and S2 is correct

c.

 S 1 is correct and S2 is not correct

d.

S1 is correct and S2 is correct

Discuss
Answer: (d).S1 is correct and S2 is correct
Q12.
Given the following statements.

S1: The grammars S → asb | bsa |ss I a and s→ asb | bsa| a are not equivalent.
S2: The grammars S→. ss| sss | asb | bsa| λ and S → ss |asb |bsa| λ are equivalent.

Which of the following is true?

a.

Sl is correct anet S2 is not correct

b.

Both S1 and S2 are correct

c.

S1 is not Correct and S2 is correct

d.

Both S1 and S2 are not correct

Discuss
Answer: (b).Both S1 and S2 are correct
Q13.
Pumping -lemma for context-free languages states :
Let Lbe an infinite context free language. Then there exists some positive integer m such that any w ∈ L with Iwl ≥m can be decomposed as w = uv xy Z with Ivxyl_________ and Ivy I such that uvz, xyZ
Z ∈ L for all z = 0, 1,2, .......

a.

≤m, ≤1

b.

≤m,≥1

c.

≥m,≤1

d.

≥m, ≥1

Discuss
Answer: (b).≤m,≥1
Q14.
The Greibach normal form grammar for the language L = {an bn+1 | n ≥ 0 } is

a.

S →  aSB, B →bB I  λ

b.

S →  aSB, B →bB I  b

c.

S →  aSB I b, B→b

d.

S →  aSB I b

Discuss
Answer: (c).S →  aSB I b, B→b
Q15.
Given the following statements:

S1: Every context-sensitive language L is recursive.
S2: There exists a recursive language that is not context sensitive.

Which statement is correct?

a.

S1 is not correct and S2 is not correct

b.

S1 is not correct and S2 is correct

c.

S1 is correct and S2 is not correct

d.

S1 is correct and S2 is correct

Discuss
Answer: (d).S1 is correct and S2 is correct
Q16.
Shift-Reduce parsers perform the following :

a.

Shift step that advances in the input stream by K(K > 1) symbols and Reduce step that applies a completed grammar rule to some recent parse trees, joining them together as one tree with a new root symbol.

b.

Shift step that advances in the input stream by one symbol and Reduce step that applies a completed grammar rule to some recent parse trees, joining them together as one tree with a new root symbol.

c.

Shift step that advances in the input stream by K(R = 2) symbols and Reduce step that applies a completed grammar rule to form a single tree.

d.

Shift step that does not advance in the input stream and Reduce step that applies a completed grammar rule to form a single tree.

Discuss
Answer: (b).Shift step that advances in the input stream by one symbol and Reduce step that applies a completed grammar rule to some recent parse trees, joining them together as one tree with a new root symbol.
Q17.
The following Context-Free Grammar (CFG) :

S → aB | bA

A → a | as | bAA

B → b | bs | aBB

will generate

a.

odd numbers of a's and odd numbers of b's

b.

even numbers of a's and even numbers of b's

c.

equal numbers of a's and b's

d.

different numbers of a's and b's

Discuss
Answer: (c).equal numbers of a's and b's
Q18.
Which of the following is true?

a.

Canonical LR parser is LR (1) parser with single look ahead terminal

b.

All LR(K) parsers with K > 1 can be transformed into LR( 1) parsers

c.

Both a and b

d.

None of the above

Discuss
Answer: (c).Both a and b
Q19.
The pushdown automation M = ( {q0, q1, q2}',{a, b}, {0, 1}, δ, q0,0, {q0}) with

δ (q0, a, 0) = {(q1,10)}

δ (q1,a, 1) = {(q1,11)}

δ (q1,b, 1) = {(q2 , λ)}

δ(q2 , b, 1) = {(q2 , λ)}

δ (q2 , A, 0) = {(q0, λ)}

Accepts the language

a.

L= {a^nb^m l n,m >=0}

b.

L= {a^nb^n l n >=0}

c.

L= {a^nb^m l n,m >0}

d.

L= {a^nb^n l n >0}

Discuss
Answer: (a).L= {a^nb^m l n,m >=0}
Q20.
Given two languages:

L1= {(ab)n,ak I n> k, k >=0}

L2 = {an bm l n ≠ m}

Using pumping lemma for regular language, it can be shown that

a.

L1 is regular and L2 is not regular

b.

L1 is not regular and L2 is regular

c.

L1 is regular and L2 is regular

d.

L1 is not regular and L2 is not regular

Discuss
Answer: (a).L1 is regular and L2 is not regular
Page 2 of 16

Suggested Topics

Are you eager to expand your knowledge beyond Theory of Computation(TOC)? We've curated a selection of related categories that you might find intriguing.

Click on the categories below to discover a wealth of MCQs and enrich your understanding of Computer Science. Happy exploring!

Computer Architecture

Unveil the science behind computer design with our Computer Architecture MCQs. Topics...

Data Science

Discover the fascinating world of extracting insights from data with our Data Science...

Web Technologies

Master the building blocks of the web with our Web Technologies MCQs. From HTML and...

Systems Programming

Decode low-level programming with our Systems Programming MCQs. These questions delve...

Computer Hardware

Explore the tangible components of computers with our Computer Hardware MCQs. Learn...

Microprocessor

Understand the heart of your computer with our Microprocessor MCQs. Topics include...

Digital Image Processing (DIP)

Delve into the techniques of enhancing digital images with our Digital Image...

Software Architecture and Design

Get a strong hold on the blueprint of software systems with our Software Architecture...

Cryptography and Network Security

Secure your knowledge of information security with our Cryptography and Network...