IMP Questions TOC PDF

Preview

Summary

Subject Name: Theory Of ComputationSubject Code: 2160704 Branch & Semester: CE-VIIMPORTANT QUESTIONS1 What is meant by “one to one” and “onto” function? Check whether function f: R ---> R+, f(x) = x2 is one to one and onto. 2 In the given relation determine the properties( reflexivity...

Description

Subject Name:

Theory Of Computation

Subject Code: Branch & Semester:

2160704 CE-VI

IMPORTANT QUESTIONS 1 2 3

4 5

6 7 8

What is meant by “one to one” and “onto” function? Check whether function f: R ---> R+, f(x) = x2 is one to one and onto. In the given relation determine the properties( reflexivity, symmetry, transitivity), which ones the relation has: R = {(1,1),(2,2),(3,3),(1,2)} and R = Ø Using Principle of Mathematical Induction, prove that for every n >= 1, n Σ i = n (n+1) / 2 i=0 Using Principle of Mathematical Induction, prove that for every n >= 1, 7 + 13 + 19 + . . . + (6n + 1) = n(3n +4) . Using Principle of Mathematical Induction, Prove that For every n >= 1. n Σ i2 = n (n+1)(2n+1)/ 6 i=1 Draw FA for regular expression: 1) (111+100)*0 2) (11+110)* 0 Compare FA, NFA and NFA- Λ with illustration. Suppose that Languages L1 and L2 are the subsets given below. Where Σ = { 0 , 1 } L1 = { x | 00 is not a substring of x } L2 = { x | x ends with 01 } Draw FAs recognizing the following languages (1) L1 - L2 (2) L1∩L2

9

10

Write definition of Finite Automata and draw FA for the strings: (i) The string with next to last symbol as 0. (ii) The string with number of 0s odd and number of 1s odd Suppose that L1 and L2 are the subsets:

Draw the Fas recognizing the following languages. • L1 ∩ L2 • L1 – L2 11

12

13

Write definition of finite automata and draw FA for the strings: (i)The string in {0,1}* ending in 10 or 11. (ii)The string corresponding to Regular expression {11}*{00}* Attempt the following : 1)Draw FA for (a + b)* baaa. 2)Write a Regular Expression for the String of 0’s and 1’s in which number of 0’s and 1’s are even. Let M1, M2 and M3 be the FAs pictured in Figure below, recognizing languages L1, L2, and L3 respectively.

Draw FAs recognizing the following languages: i. L1 U L2 ii. L1 ∩ L2 iii. L1 - L2 iv. L1 ∩ L3 v. L3 - L2

14

15 16

17 18

For following NFA find minimum FA accepting same language:

What do you mean by Regular Language? Explain the application of the Pumping Lemma to show a Language is Regular or Not.[ For the following Regular Expression draw an NFA- Λ recognizing the corresponding languages. (i) (00 + 1)* (10)* (ii) 001*0*11 Prove Kleene’s Theorem Part 1 with illustration. Define Pumping Lemma for Regular Languages. Use Pumping Lemma to show that following languages are not regular. L = { 0n 12n / n > 0 } L = { wwR / w ε {0,1}* }

19

20

Convert NFA-^ to NFA and DFA. Initial State: A , Final State: D [LJIET] [May-2015]

Minimize the following DFA (If Possible).

21

22

23 24 25 26 27

28

29

Consider the following NFA-^. Q δ (q,Λ) δ(q, 0) δ(q, 1) -A {B} {A} Ǿ B {D} {C} Ǿ C Ǿ Ǿ {B} +D Ǿ {D} Ǿ [1] Convert this NFA-^ into its equivalent NFA. [2] Take this NFA as an input and convert it into equivalent DFA. Convert following NFA- Λ to NFA and FA. Q δ (q,Λ) δ(q, 0) δ(q, 1) A {B,D} {A} Ǿ B Ǿ {C} {E} C Ǿ Ǿ {B} D Ǿ {E} {D} E Ǿ Ǿ Ǿ Construct a Mealy machine which will do 2’s complement of a binay number. Construct a Mealy machine which can output Even ,Odd according as total numbers of 1’s encountered is even or odd. The input symbols are 0 and 1. Design a Moore and Mealy machine for a binary input sequence such that if it has a substring 101 the machine outputs A if input is 110 it outputs B otherwise it outputs C. Top down and bottom up parsing. Find CFG for the following languages. 1. L = { ai bj ak | j > I + k } 2. L = { ai bj ck | I = j or j = k } Given the Context Free Grammar G, find a CFG G’ in Chomsky Normal Form generating L(G) – { } S → SS | A | B A → SS | AS | a B → /\ For the following CFG’s, describe the language it accepts.

30

31 32

1. S  SS | XaXaX | ^ X  bX | ^ 2. S  aM | bS M  aF | bS F  aF | bF | ^ 3. S  aS | bS | a | b | ^ Given the Context Free Grammar G, find a CFG G’ in Chomsky Normal Form generating L(G) – { } 1) S → aY | Ybb | Y X → /\ | a Y → aXY | bb | XXa 2) S → AA A → B | BB B → abB | b | bb Prove that following CFG is Ambiguous and convert it into unambiguous. S ->S + S | S * S | (S) | a Define Context Free Grammar(CFG). Design CFG for Generating Following Language: (1) For Balanced Parenthesis (2) Set of even length strings in {a, b, c, d}* with two middle symbol equal.

33

34 35 36 37 38 39

Given the CFG G, find a CFG G’ in Chomsky Normal form generating L(G) – { Λ}. SA | B | C A aAa | B B bB | bb C aCaa | D D baD | abD | aa For the language L={set of strings over alphabet {a, b} with exactly twice as many a’s as b’s} design a PDA (Push Down Automata) and trace it for the sring “abaabbaaaaabaab” For the language L={ aibjck | i, j, k ≥ 0 and i + j = k } design a PDA (Push Down Automata) and trace it for String “bbbbbccccc” Design and draw a deterministic PDA accepting strings with more a’s than b’s. Trace it for the string “abbabaa” . For the language L = { xcxr / x ε {a,b}* } (Palindrome with middle character=c),Design a PDA(Push Down Automata) and trace it for string “abacaba” . Write PDA for following languages: { x ϵ { a,b,c}* | na(x) < nb(x) or na(x) < nc(x) }. Give transition table for deterministic PDA recognizing the following language { ai bj ck | i, j, k ≥ 0 and j = i or j = k }.

40 41

42 43 44 45 46 47 48

49 50

51 52 53 54

QUESTIONS NOT DONE BUT IMPORTANT Define Turing Machine. Describe its capabilities. Also write short notes on Universal Turing Machine Write Short note on Following: (i) Halting Problem (ii) Church Turing Thesis Define Turing Machine. Draw TM for accepting Palindrome Strings in {a,b}*. Draw the TM to copy string and delete a symbol. Draw a transition diagram for a Turing machine accepting the following language { x є { a, b, c }* | na(x) = nb(x) = nc(x) } Draw the TM for L = {ss | s ∈ (a, b)* } Draw a Turing Machine™ to accept Palindromes over {a,b}. (Even as well as Odd Palindromes) Answer the following : Explain time and space complexity Define: [1] Basic complexity Classes [2] Primitive Recursive Functions [3] The Time and Space Complexity of a Turing Machine Explain unbounded minimization and μ recursive functions Explain the following 1. Primitive Recursive Operation & Function. 2.μ Recursive Functions. Write Short Note on Following:NP-Hard and NP-Complete Language Explain in Brief: Basic complexity Classes Write short note on the Sets P, NP, Pspace and NPSpace. Explain Cook’s Theorem....