Theory Of Computation MCQ - Context free languages

1:  

Correct hierarchical relationship among context- free, right-linear, and context-sensitive language is

A.

context-free  ⊂ right-linear  ⊂ context-sensitive

B.

context-free  ⊂ context-sensitive  ⊂ right-linear

C.

context-sensitive  ⊂ right-inear  ⊂context-free

D.

right-linear  ⊂context-free  ⊂context-sensitive

 
 

Option: D

Explanation :

Click on Discuss to view users comments.

Write your comments here:



2:  

In the following grammar :

x : : = x  ⊕ y |  4
y : : = z * y I 2
z : : = id


which of the folowing is true ?

A.

⊕ is left associative while * is right associative

B.

Both ⊕ and * are left associative

C.

⊕ is right associative while * is left associative

D.

None of these

 
 

Option: A

Explanation :

Click on Discuss to view users comments.

Preeti said: (7:23pm on Wednesday 20th November 2013)
Answer A is correct.
anita said: (1:20pm on Tuesday 2nd May 2017)
ans a is correct
Ankit said: (1:42am on Thursday 24th August 2017)
A answer is correct
Akhil Babu said: (9:46pm on Monday 26th February 2018)
Option A is currect.
Yudhik said: (7:23am on Tuesday 24th April 2018)
A is the correct answer

Write your comments here:



3:  

Which of the following CFG's can't be simulated by an FSM ?

A.

S --> Sa | b

B.

S  --> aSb | ab

C.

S --> abX,  X --> cY,  Y --> d | aX

 

D.

None of these

 
 

Option: B

Explanation :

Option (b) generates the set {an bn ,n=1,2,3 ....}which is not regular ,Option (a) is left linear where as option (C) is right linear .

Click on Discuss to view users comments.

Write your comments here:



4:  

ADG is said to be in Chomsky Form (CNF), if all the productions are of the form A --> BC or
A --> a. Let G be a CFG in CNF. To derive a string of terminals of length x , the number of productions to be used is

A. 2x - 1
B. 2x
C. 2x + I
D. None of these
 
 

Option: A

Explanation :

Click on Discuss to view users comments.

kavita said: (1:11pm on Sunday 9th June 2013)
why option a?
Akhil Babu said: (9:55pm on Monday 26th February 2018)
So in each step when we try to derive a string, there are two possibilities1) Either at every step we are increasing number of variables(Non terminals) by 12) OR we are going to increase number of terminals by 1Therefore we first try to get string of variables whose length is equal to the given string, in this procedure the number of steps required = n-1 and from there on we keep on replacing every variable with a terminal, in this procedure the number of steps requires =nSo total = n -1 n =2*n-1 steps

Write your comments here:



5:  

Which of the following statements is correct?

A.

A = { If an bn  | n = 0,1, 2, 3 ..} is regular language

B.

Set B of all strings of equal number of a's and b's deines a regular language

C.

L (A* B*)∩ B gives the set A

D.

None of these

 
 

Option: C

Explanation :

If we include A and B in a set and if we write A*  it means except  then A i.e. B  same as  B*  means except then B i.e.A so  if we intersect (A*B*)  and B   then get A  because in any regular language

 if we write A-B then A-B=A intersection B'  so if we intersect A and B means A-B  So intersection of (A*B*) and B  = (BA) intersection B  means (BA)-B' and B'=A so (BA) intersection(A)=A
So ans is (C) 

Click on Discuss to view users comments.

Abdul said: (12:46am on Wednesday 7th December 2016)
What if A does not contain the empty string?

Write your comments here:




Syllabus covered in this section is-

  • Regular languages and finite automata
  • Context free languages and Push-down automata
  • Recursively enumerable sets and Turing machines
  • Undecidability, NPcompleteness
  • Models of computation-Finite Automata
  • Pushdown Automata
  • Non-detenninism and NFA. DPDA and PDAs and Languages accepted by these Structures
  • Grammars, Languages,
  • Non- computability and Examples of non-computable problems

This Section covers Theory of Computation Questions Answers .These questions can be used for the preparation of various competitive and academic exams like

  • UGC NET Computer Science
  • Pre PhD Entrance Exam
  • DOEACC Exams
  • Kendriya Vidyalaya Sangathan Entrance Exam
  • Undergraduate Computer Science Examinations
  • GATE Computer Science
  • Post Graduate Computer Science Test
  •  PhD Entrance Exam
  • Computer Engineering
  • National Eligibility Test (NET)
  • State Eligibility Test (SET)

Who can benefit

  • Theory of Computation Objective Questions Answers can be used by any student who is preparing for PhD entrance exam, pre PhD entrance exam, entrance exam or any other such exam.
  • Any student who is preparing for DOEACC exams can also use Theory of Computation questions answers for preparation of his exams.
  • Automata Theory mcq can be useful for the students who are pursuing any undergraduate or post graduate degree in computer science like BE, ME , Btech, Mtech, .BSc, MSc, BCA, MCA, BS, MS  or any other such degree
  • Theory of Computation mcq with answers and explanation can also be useful for the students who are preparing for any competitive exam or recruitment exams like GATE Computer Science, UGC NET Computer Science, Kendriya Vidyalaya Sangathan PGT exam, PSU, IES or any other such exam.
  • Theory of Computation multiple choice questions answers can also be used by any candidate who wants to gain credits in Theory of Computation in BS Computer science or MS Computer science.
  • Theory of Computation mcq questions answers can be used for the preparation of National Eligibility Test (NET) and State Eligibility Test (SET).
  • You can download Theory of Computation mcq pdf from this site.
  • You can get access to Theory of Computation multiple choice questions answers EBook.

Various Search Terms Used For This Section Are

  • Theory of Computation Quiz Questions With Answers

  • Theory of Computation Exam Questions Answers

  • Theory of Computation Mcq Questions Answers

  • Theory of Computation Mcq Pdf Download

  • Automata Theory Questions Answers

  • Automata Theory Quiz