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

Discrete Structures & Optimization MCA paper Dec 2020

Image
Subject Code : - PGCA 1917 Subject Name : - Discrete Structures & Optimization Date of Examination : - December 2020 Class : - MCA 1st Instructions to Candidates Section A   is Compulsory consisting of TEN questions carrying TWO marks each. Section B & C have FOUR questions each. Attempt any FIVE questions from SECTION B & C carrying TEN marks each. Select at least TWO questions from SECTION B & C SECTION-A What are ordered pairs? Write the concept of Hashing Functions? Discuss rings in discrete structure. What is meant by isomorphic in graph theory? Give an example of a Finite graph. Write about the principle of Inclusion. Define an undirected graph. What is the Indegree of the graph? What is the use of the Karnaugh Map? What do you mean by chromatic number? SECTION-B Give the properties of relations and functions? Prove that a graph G with e=v-1 that has no circuit is a tree. How eulerian chains and cycles are related to a connected graph? Let ...
Read more

Discrete Structure and Optimization MCA paper Nov 2021

Subject Code: - PGCA 1917 Subject Name: - Discrete Structure and Optimization 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 Prove the following : X ∩ (Y ⋃ Z) = (X ∩ Y) ⋃ (X ∩ Z) How many symmetric relations will there be on a set of three elements? Investigate the function f (x) = x 2 + 3x + 2 for increasing and decreasing function in its entire domain. Prove that the set {0,1,2} forms a field with respect to addition and multiplication modulo 3. Simplify the following Boolean functions using the Karnaugh map: F = x'y'z' + x'yz' + xyz' + xy' z' Find the number of diagonals...
Read more

Advanced Database Management System MCA Paper Dec 2020

Image
Subject Code : - PGCA 1953 Subject Name : - Advanced Database Management System Date of Examination : - December 2020 Class : - MCA 1st Instructions to Candidates Section A  is Compulsory consisting of TEN questions carrying TWO marks each. Section B & C  have FOUR questions each. Attempt any FIVE questions from  SECTION B & C  carrying TEN marks each. Select at least TWO questions from  SECTION B & C SECTION-A What do you mean by redundancy & how can it be avoided? What is the difference between the strong entity and weak entity set? Discuss the four data allocation strategies in the case of Distributed Databases. What is Relational Calculus? What is a NoSQL database? List any 2 NoSQL databases. Differentiate between a super key and a candidate key. What is Multivalve dependence? What is Spatial Database? Differentiate between 2-tier and 3-tier client-server architecture of database systems. List the different activities of a Database Administra...
Read more