Theory of Computation MCA paper Nov 2021

  • Subject Code: - PGCA 1927
  • Subject Name: - Theory of Computation
  • Date of Examination: - Nov 2021
  • Class: - MCA 3rd
  • Exam Mode: - Online

Instructions to Candidates

  1. Attempt any FIVE question(s), each question carries 14 marks.

QUESTIONS

  1. State and prove Principle of Mathematical Induction.
    2.
    1. Prove that ∈ + RR* = R* = ∈ + R*R
    2. Prove that (P + Q)* = P*Q*
    3.
  3. What are Context Free Grammars? How are they different from context free language? Discuss various normal forms for context free grammars in brief.
    4.
    1. State the principle of pumping lemma. Also discuss its various applications.
    2. Reduce the given CFG S → abSb/a/aAb and A → bS/aAAb to Chomsky Normal Form (CNF).
    5.
    1. Differentiate between recursively enumerable and recursive languages.
    2. What are Context Sensitive languages? Explain
    6.
    1. Design a Turing Machine that can add two unary strings.
    2. Design a Turing Machine which can find transpose of a binary string.
    7.
    1. Prove the following property of regular expressions: R + R = R.
    2. State whether the following statement is true or not. Justify your answer as well: If L and M are regular languages then L + M, LM and L* are also regular.
    8.
  8. Prove that the class of languages accepted by finite automata is closed under:
    1. Union.
    2. Complementation.
    3. Intersection.
    9.

ANSWERS:

Q1.

Top

Comments

Post a Comment

Popular posts from this blog

Programming in Python MCA paper Nov 2021

Subject Code: - PGCA 1951 Subject Name: - Programming in Python Date of Examination: - Nov 2021 Class: - MCA 1st Exam Mode: - Online Instructions to Candidates Attempt any FIVE question(s), each question carries 14 marks. QUESTIONS Write a function in Python, INSERTQ(A,data) and DELETEQ(A) for performing insertion and deletion operations in a Queue. A is the list used for implementing queue and data is the value to be inserted. How can you traverse, insert and delete elements from an array using inbuilt functions. Elaborate using Python code. Write a Python program to delete the first occurrence of the given word in a List, where words can repeat. Write a Python program to check whether a string is a palindrome or not using recursion. ...
Read more

Advanced JAVA MCA paper May 2021

Subject Code: - PGCA 1918 Subject Name: - Advanced JAVA Date of Examination: - May 2021 Class: - MCA 2nd Exam Mode: - Online Instructions to Candidates Attempt any FIVE question(s), each question carries 14 marks. QUESTIONS Define servlet? How servlet is different from applet? Discuss about HttpServletRequest and HttpServletResponse classes and its methods. What is struts? Explain the features, architecture and working diagram of struts framework What are the elements of JSP page? Give the purpose and role of each element also show the use of request and response objects in JSP with proper JSP example. What are cookies? Compare the session tracking with cookies and session object with their pros and cons. How to create Javabean? Describe various techniques available for using...
Read more

Computer Networks BCA paper Nov 2021

Subject Code: - UGCA 1913 Subject Name: - Computer Networks Date of Examination: - Nov 2021 Class: - BCA 3rd Exam Mode: - Online Instructions to Candidates Attempt any FIVE question(s), each question carries 12 marks. QUESTIONS What is Unguided Network Media? Explain its types, merits and demerits. Why multiple access is required in LAN technologies? Compare FDM, TDM and SDM. Differentiate between circuit, message and packet switching. What is OSI reference model? Compare it with TCP / IP model. Discuss the various issues in session and presentation layer. Differentiate between simplex, half duplex and full duplex channels. Define routing. Explain any one algorithm of routing. Write a note on flow control and buffering. ...
Read more