Theory Of Computation MCQ - Context free languages

6:  

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

A. Q has to be regular
B. Q cannot be regular
C. Q need not be regular
D. Q cannot be a CFL
 
 

Option: C

Explanation :

Click on Discuss to view users comments.

KALPANA SINGH said: (10:57pm on Sunday 4th June 2017)
As per decision rule only union, intersection and difference with other language and regular language are regular but no rule for concatenation it must be regular Q
AKASH MAHAJAN said: (11:07pm on Monday 18th September 2017)
by defination A is correct i.e Q has to be regular.Regular Grammer is closed under concatenation property, ie if A

Write your comments here:



7:  

 A class of language that is closed under

A. union and complementation has to be closed under intersection
B. intersection and complement has to be closed under union
C. union and intersection has to be closed under complementation
D. both (A) and (B)
 
 

Option: D

Explanation :

Click on Discuss to view users comments.

Write your comments here:



8:  

The productions
E—>E+E
E—>E—E
E-->E*E
E —> E / E
E —> id

A. generate an inherently ambiguous language
B. generate an ambiguous language but not inherently so
C. are unambiguous
D. can generate all possible fixed length valid computation for carrying out addition, subtraction, multipication and division, which can be expressed in one expression
 
 

Option: B

Explanation :

Click on Discuss to view users comments.

PENCHAL said: (7:22am on Monday 20th November 2017)
A CFL language L is inherently ambiguous if every CFG for L is ambiguous.in the problem every CFG L is ambiguous so the correct answer is A

Write your comments here:



9:  

 Which of the folowing definitions below generates the same language as L, where
L = {xn yn such that n > = 1} ?

I. E —> xEy | xy

II. xy | (x+ xyy+)

III .x+y+

A. I only
B. I and II
C. II and III
D. II only
 
 

Option: A

Explanation :
II generates strings like xxyyy, which are not supposed to be.

III generates strings like xyy, which are not supposed to be.
I can be verified to generate all the strings in L and only those.


Click on Discuss to view users comments.

Write your comments here:



10:  

Following context free grammar
S —> aB | bA 
A —>b | aS | bAA
B —> b | bS | aBB 

generates strings of terminals that have

A. equal number of a's and b's
B. odd number of a's and odd number b's
C. even number of a's and even number of b's
D. odd number of a's and even number of a's
 
 

Option: A

Explanation :
S —> aB —> aaBB-->aabB —> aabb
So (b) is wrong. We have
S --> a B —> a b So (c) is wrong.
A careful observation of the productions will
reveal a similarity. Change A to B, B to A, a to b
and b to a. The new set of productions will be
the same as the original set. So (d) is false and
(a) is the correct answer.

Click on Discuss to view users comments.

manjureka said: (2:12pm on Friday 12th June 2015)
Option A also wrong..why because the string aB>abs>abbA>abbbAA>abbbbb it may confuse please give me the clear solution for me.....
TJ said: (5:48pm on Wednesday 7th October 2015)
the given answer is incorrect. and for the above answer A, grammer must be A->a|aS|bAA and for S and B same as above. then it will work.
anubhav said: (1:37am on Thursday 30th June 2016)
option A is wrong as this grammar is accepting "bb" in which no. of a's and b's are not equal...
mozhi said: (4:33pm on Thursday 4th May 2017)
Suppose we derive llike S —> bA

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