Name of the University : University of Pune
Name of the College : MIT Arts Commerce & Science College
Degree : B.SC
Department : Computer Science
Subject Code/Name : CS-332/CS342 Theoretical Computer Science and Compiler Construction-I and II
Year : III
Semester : V
Document Type : Question Bank
Website : mitacsc.ac.in
Download Model/Sample Question Paper :
CS332 : www.pdfquestion.in/uploads/mitacsc.ac.in/3829.-TYBSc_TCS_SemI_Que_Bank.docx
CS342 : www.pdfquestion.in/uploads/mitacsc.ac.in/3829.-TYBSc_TCS_SemI_Que_Bank.doc
MITS Theoretical Computer Science Question Paper
Chapter 1)
Preliminaries
1.Write a power set of A where A={1,2,3}
2.What is the value of n, where |e|=n-
3.Let A= {1,2,3} and B={2,4,3} then write the Cartesian product –
Related : MIT Arts Commerce & Science College CS346 Business Applications B.SC Question Bank : www.pdfquestion.in/3846.html
4.What is the value of n, where n=| e |.
5.Define the term language.
6.List any two properties of sets.
7.Define the term empty string with example.
8.Define suffix and list all proper suffixes of the string “abcd”.
9.What do you mean by diagonalization in the context of infinite sets-
Chapter 2)
Finite Automata
1.Write a mapping of d in case of NFA and DFA both.
2.Construct NFA for language L where L={a(a+b)*b}
3.Write 5 tuples of DFA and NFA.
4.Construct NFA without e for language L where L=(0+1)*01.
5.Write the condition for string acceptance in FA.
6.Construct NFA for language L where L=01*(01)*+1.
7.State equivalence theorem of NFA and DFA.
8.Define e -closure (q).
9.Construct NFA with e – transitions for ab*+ba*.
Chapter 3)
Regular Languages
1.Define TM.
2.Give diagrammatic representation of TM.
3.What is difference between TM and FA.
4.Every language accepting by TM is regular. State true or false.
5.Give the snapshot of TM and obtain instantaneous description.
6.Explain move of TM.
7.Define : ID of a turing machine.
8.Define language accepted by a turing machine.
Chapter 4)
Context Free Grammar & Languages
1.Define nullable symbol.
2.Define useless symbol.
3.What yield the derivation tree given below-
4.Define unit production.
5.Every CFL is regular language. State True or False.
6.Define ambiguous grammar.
7. Define Left linear grammar.
8.What yield the derivation tree given below-
9. Define inherently ambiguous context free language.
Chapter 5)
Pushdown Automata
1.Write formal definition of DPDA.
2.Write formal definition of NDPDA.
3.The class of language accepted by DPDA and NPDA is same justify.
4.Give diagrammatic representation of PDA.
5.Define ID for PDA.
6.State formal definition of PDA.
7.Differentiate between DPDA and NPDA.
8.DPDA and NPDA are not equivalent. Justify.
9.State two methods for defining language accepted by PDA.
10. State any two difference between PDA and FA.
11. How d function is mapped in PDA?
12. Write tuples of PDA.
13. Class of CFG and PDA is same. Justify True/ False.
5 Mark Questions
14. Construct PDA for L = {ax by cz | x=2y+z,y,z>=1}.
15. Construct PDA for L = {an b2n ck | n>=1,k>=0}.
16. Construct PDA for L = {am bn cn+2 dm | n>=1,m>=1}.
17. Construct PDA for following CFG
S? aAb | As
A? Bb | a
B? Sa | b
18. Construct PDA for L = {an bn +1 | n>=1}.
19. Construct PDA for L = {an b2n +1 | n>=1}.
20. Construct PDA for L = {0m 1n 2k | m,n,k>=1,m=n+k}.
21. State the equivalence theorem of PDA and CFL. Also construct a PDA for a language odd palindrome.
22. Show that DPDA and NPDA are not equivalent with an appropriate example.
23. Construct PDA over {0,1} to accept a string which does not contain the substring “00”.
24. Construct PDA for L = {am bn cm+n | n>=1,m>=1}.
25. Convert CFG to PDA.
S? aB | bA
A? a | aS | bAA
B? b | bS | aBB
Chapter 6)
Turing Machine
1 Mark Questions
1. Define TM.
2. Give diagrammatic representation of TM.
3. What is difference between TM and FA.
4. Every language accepting by TM is regular. State true or false.
5. Give the snapshot of TM and obtain instantaneous description.
6. Explain move of TM.
7. Define: ID of a turing machine.
8. Define language accepted by a turing machine.
5 Mark Questions
9. Construct TM accepting following language
L = {am bn | m>n and n>0}
10. Construct TM accepting following language
L = {am bn | n>=m and m>=1}
11. Construct TM accepting following language
L = {0i 1 2i+2 | i>=0}
12. Design a TM to recognize well- formedness of parenthesis (only
round open close brackets).
13. Construct TM accepting following language
L = {02n 2n | n>=1}
14. Design a TM that recognizes the well- formedness of parenthesis
over {(,)}
15. Construct TM accepting following language
L = {0n 1n 0 n | n>=1}.