2023 2024 Student Forum > Management Forum > Main Forum

 
  #2  
12th February 2016, 03:29 PM
Super Moderator
 
Join Date: Apr 2013
Re: Theory of Computation IGNOU

The Indira Gandhi National Open University, known as IGNOU, is a distance learning national university located in IGNOU road, Maidan Garhi, New Delhi, India


CS73 : THEORY OF COMPUTER SCIENCE

Time: 3 hours
Maximum Marks: 75

Note : Question number 1 is compulsory. Answer any three questions from the rest.
1. (a) Define finite automata. Explain the parts of automata. (6)

(b) Define CFG, also giving an example. (6)

(c) State the satisfiability problem (SAT). Also explain SAT using an example. (6)

(d) (i) Give the regular expression for a language over the alphabet {a, b}, of strings of odd length.
(ii) Give the regular expression for a language over the alphabet {0, 1}, of strings which have '1' as the third symbol from left.
(iii) Display the typical state transition for a Moore machine, expiaining the labels used. (6)

(e) Consider the following productions:
S → aB/bA
A → aS/bAA/a
B → bS/aBB/b
For the string aabbbaabba, find
(i) the left most derivation
(ii) Parse tree. (6)

2. (a) State and prove the Pumping lemma for regular expressions. (8)

(b) for two recursive languages L1 and L2 determine whether or not L1 ∩ L2 is Turing Decidable. (4)

(c) Describe recursive production through an example. (3)

3. (a) Differentiate "Partial" function from "Total" function. Also give one example for each of them. (4)

(b) Define an NP-complete problem with an example. (3)

(c) Give the state transition graph and state transition table for the elevator controller that serves two floors. (8)

4. (a) Determine the Closure property of CFLs under the following set operations : (9)
(i) Union
(ii) Kleene star
(iii) Complementation

(b) Prove that, if f(x) = 8x3+5x2+7, then (6)
(i) f(x) = ω(x), and
(ii) f(x) = ω(x2)

5. (a) Explain the halt state version of a TM. (7)

(b) Build a PDA that accepts the language odd palindrome over the alphabet {0, 1}. Give the computation sequence for the input 0110110. (8)


Quick Reply
Your Username: Click here to log in

Message:
Options

Thread Tools Search this Thread



All times are GMT +5. The time now is 12:56 AM.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2024, vBulletin Solutions Inc.
SEO by vBSEO 3.6.0 PL2

1 2 3 4