Scribd
Upload
48 views2 pages

Imp Toc Question

The document contains a series of important questions related to the Theory of Computation, including topics like ambiguous grammars, context-free grammars (CFG), pushdown automata (PDA), Turing machines, and various computational problems. It also includes multiple-choice questions regarding the properties of languages and automata. The questions cover both theoretical concepts and practical applications in the field of computer science.

Uploaded by

khushidasar8
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
48 views2 pages

Imp Toc Question

The document contains a series of important questions related to the Theory of Computation, including topics like ambiguous grammars, context-free grammars (CFG), pushdown automata (PDA), Turing machines, and various computational problems. It also includes multiple-choice questions regarding the properties of languages and automata. The questions cover both theoretical concepts and practical applications in the field of computer science.

Uploaded by

khushidasar8
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd

Theory of Computation (CS-501) Imp Question

Q1. What is a ambiguous grammar?


Q2. Construct CFG for L = L1 union L2 where Ll = {anbm | m, m > 0) and L2 = An strings having 01 as a
substring over (0,1)
Q3 Construct CFG in CNF equivalent to G = ({ S,A, B,D} , {0,l}, P,S) where P = { S0AB, AaD | lAD,
B 0, D 1}
Q4 If SaSb | aAb , AbAa , Aba. Find out the CFL.

Q5Design a PDA for the language L = a2nbn , where a and b belongs to the alphabet
Q6 What is the significance of PDA?
Q7Define Instantaneous description (ID) in PDA?
Q8 Design a PDA for the language L = anbn , where a and b belongs to the alphabet.
.
Q9 Construct a Turing Machine for L = {an b2n+2 | n > 1}
Q10 Define tractable and intractable problems.
Q11 Prove that a language L is recursive if and only if L and are recursively enumerable.
Q12 Design a Turing Machine for the Language L = anbn , where a and b belongs to the alphabet
Q13 Explain Halting Problem of Turing Machine
Q14 Explain Post Correspondence Problem
Q15Explain Various Properties of Recursive Language

IMP QUIZ

Q.1 DPDA and NPDA


A. Power is different
B. Power is same
C. Not Related
D. None of the above
Q.2 Halting problem of Turing machine is
A. Decidable
B. Undecidable
C. Ambiguous
D. None of the above
Q.3 Push down machine represents
A. Type 0 Grammar
B. Type 1 grammar
C. Type-2 grammar
D. Type-3 grammar
Q.4 which of the following statements in true?
(a) If a language is context free it can always be accepted by a deterministic push-down
automaton
(b) The union of two context free languages is context free
(c) The intersection of two context free languages is context free
(d) The complement of a context free language is context free
Q.5 LBA means
(a) Linear bounded automata
(b) Line bounded automata
(c) Linear branded automata
(d) Linear bounded autonomy
Q.6 NPC Means
(a) Non deterministic polynomial complete
(b) deterministic polynomial complete
(c) Non polynomial complete
(d) Non deterministic complete
Q. 7 Recursive and RE Languages are
A. Power is different
B. Power is same
C. Not Related
D. None of the above
Q.8 which of the following statements in true?
(a) If a language is context free it can always be accepted by a deterministic push-down
automaton
(b) The union of two Regular languages is context free
(c) The intersection of two context free languages is context free
(d) The complement of a context free language is context free
Q.9 which of the following statements in true?

L1= a^m b^n / m!=n


L2= a^m b^n / m=2n

A. Both are CFG


B. only L1 is CFG
C. Only L2 is CFG
D. none of These

Q. 10 Turing Machine represents


A. Type 0 Grammar
B. Type 1 grammar
C. Type-2 grammar
D. Type-3 grammar

You might also like