Gujarat Technological University 2010 M.C.A Theory of Computation Remedial ember-, (ks 70) - Question Paper
Seat No. Enrolment No.
GUJARAT TECHNOLOGICAL UNIVERSITY
MCA. Sem-II Remedial Examination December 2010
Subject code: 620007
Subject Name: Theory of Computation Date: 22 /12 /2010 Time: 10.30 am - 01.00 pm
Total Marks: 70
1. Attempt all questions.
2. Make suitable assumptions wherever necessary.
3. Figures to the right indicate full marks.
Q.1 (a) 1. Prove the statement (p V q) r and (p -> r) V (q -> r) are logically equivalent
03
02
02
04
03
03
2. Show that for any integer n > 2, there is a primep that must satisfy n <p < n!
3. Explain the logical quantifiers and quantified statement.
(b) 1. Define Fibonacci function f) in terms of recursion. Prove that for every n > 0 fn) < ( 5/3 )n
2. Define Regular language & give the Regular expression corresponding to the strings having even length
Q.2 (a) 1. Given regular expressions are
* * 1 r = 0 + 1 and = 01* + 10* + 1* + (0*1)*
(1) Give the strings corresponding to r but not in 5.
(2) Give the strings corresponding to 5 but not in r.
(3) Give the strings corresponding to both r and 5.
2. Give regular expression corresponding to strings ending in 1 & not
01
03
04 03
04
03
containing 00.
3. Construct a DFA that recognizes the language
L = { x e {0,1}* | |x| > 3 and 3rd symbol from the right side in x is 1}
(b) 1. Define NFA with suitable example in details. Also differentiate NFA and DFA.
2. Show that, any Language is recognized by an NFA if and only if it is recognized by a DFA
OR
(b) 1. Calculate and define recursive definition of extended notation of 5 for NFA.
2. Show that any NFA has its equivalent DFA, accepting the same language L.
Q.3 (a) Prove that any regular language can be accepted by a finite automaton with all 07 details
2. For the following finite automaton calculate r(1, 3, 1) and r(3, 2, 1). 02
|
a |
 |
|
a | |
 |
a b |
2. Define Myhill and Nerodes Theorem for the regular languages and show that 03
OR
L = { ww | w e {a, b} } is non regular.
(b) Find the unambiguous context-free grammar for the language of all algebraic 07 expressions involving parenthesis, the identifier a, and the following four binary operators +, -, *, & /.
Q.4 (a) Construct a DPDA to accept the language of strings with more as than bs given by 07
L = { x e {a, b}* | na(x) > nb(x) }
(b) 1. Remove the A-productions from the CFG with given productions and find a CFG 04 generating the equivalent language without A.
S AB | A A aASb | a B bS
OR
Q.4 (a) Design the PDA & its corresponding CFG for the language that accepts simple 07 palindromes given by L = { xcxr | x e {a, b} }
(b) Convert the CFG with following productions to CNF: 07
D aDa | bDb | A
Q.5 (a) Explain Pumping Lemma for the Context-Free Language and verify the language 07
L = { anbncn | n > 1 }is Context-free or not.
recursive
OR
Q.5 (a) Construct a Turing Machine that accepts the language of palindromes over {a, b} Also 07 specify the moves to trace the strings abaa, abba, aabaa.
2. Define Turing Machine and give its advantages. 02
kifkifkifkifkifkifk
2
|
Attachment: |
| Earning: Approval pending. |
