TOC(CS8501) UNIT IV MCQ PDF

Preview

Summary

Multi Choice Questions and Answers for UNIT IV - as per regulation 2017 ...

Description

JAYA ENGINEERING COLLEGE DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING MULTI CHOICE QUESTIONS AND ANSWERS SUBJECT/CODE: THEORY OF COMPUTATION/CS8501 CLASS: III YR CSE UNIT IV – PROPERTIES OF CONTEXT FREE LANGUAGES 1) How to simplify the Context free grammar? (A) Eliminate useless productions (B) Eliminate Unit productions (C) Eliminate empty productions (D) All the above mentioned Answer (D) 2) When production is said to be useful symbol? (A) It is reachable from Start symbol. (B) It generate terminals. (C) Both of above. (D) None of the above. Answer (C) 3) In context to the process of removing useless symbols, which of the following is correct? (A) remove the Nullable variables (B) remove the unit productions (C) eliminate products which yield no terminals (D) eliminate products not reachable from start symbol Answer (C) and (D) 4) Which is called Unit production? (A) A--> B (B) A-->a (C) A-->aA (D) B-->CD Answer (A) 5) Which production is called empty production? (A) A --> ε called empty production (B) A--> B ,B--->a (C)A--> BC , B and C not generate any terminals (D) A-->c Answer (A) 6) Let G be a grammar. When the production in G satisfy certain restrictions, then G is said to be in ___________. (A) restricted form (B) parsed form (C) normal form (D) None of them Answer (C) 7) When grammar is said to be Chomsky Normal Form grammar?

(A) Productions are in form A-->BC or A-->a (B) Productions are in form A-->B or A-->Ca (C) Productions are in form A-->a or A-->aBC (D) Productions are in form A-->BCDE or A-->a Answer(A) 8) Given grammar G: (1)S->AS (2)S->AAS (3)A->SA (4)A->aa. Which of the following productions denies the format of Chomsky Normal Form? (A) 2,4 (B) 1, 2, 3, 4 (C) 1,3 (D) None of them Answer(A) 9) The context free languages are closed under: (A) Union (B) Concatenation (C) closure (D) Homomorphism and Inverse Homomorphism Answer: All of above 10) The context free languages are not closed under: (A) Intersection (B) Complementation (C) Both of above (D) None of them Answer(C) 11) When grammar is said to be Griebach Normal Form grammar? (A) Productions are in form A-->BC or A-->a (B) Productions are in form A-->B or A-->Ca (C) Productions are in form A-->a or A-->aB or A-->terminal followed by Set of Variables (D) Productions are in form A-->BCDE or A-->a Answer: (C) 12) Every grammar in Chomsky Normal Form is (A) regular (B) context sensitive (C) context free (D) None of the above Answer: (C)

13) What is the use of pumping lemma ? (A)Prove languages are not regular (B)Prove languages are not context free languages (C)Both of above (D)None of them Answer: (C) 14) Given Grammar: S→ A, A→ aA, A→ e, B→ bA. Which among the following productions are Useless productions? (A)S→A (B)A→aA (C)A→e (D)B→bA Answer: (D) 15) Given:S->...->xAy->...->w. if ____________, then A is useful, else useless symbol. (A)A is a non terminal (B)A is a terminal (C)w is in language of G. (D)w is not in language of G Answer: (C) 16) Given grammar:S→aS|A, A→a , B→aa. Find the number of variables reachable from the Starting Variable? (A)0 (B)1 (C)2 (D)3 Answer: (B) 17) Find generating symbol in Given grammar G: S→ aS|A|C, A→a, B→aa , C→aCb (A){C} (B){S,A,B} (C){A,B} (D) {S} Answer: (B) 18) Given a Grammar G:S->aA,A->a,A->B,B->A,B->bb. Which among the following will be the simplified grammar? (A) S->aA|aB, A->a, B->bb (B) S->aA|aB, A->B, B->bb (C) S->aA|aB, A->a, B->A (D) None of the mentioned Answer: (A)

19) Which of the following does not have left recursions? (A)Greibach Normal Form (B)Chomsky Normal Form (C)Backus Naur Form (D)All of the mentioned Answer: (A) 20) Which of the following grammars are in Chomsky Normal Form? (A)S->AB|BC|CD, A->0, B->1, C->2, D->3 (B)S->AB, S->BCA|0|1|2|3 (C)S->ABa, A->aab, B->Ac (D)All of the mentioned Answer: (A) 21) Let G be a grammar: S->AB|e, A->a, B->b.Is the given grammar in CNF? (A)Yes (B)No Answer: (A) 22) Which of the expressions correctly is an requirement of the pumping lemma for the context free languages? (A)uv^nwx^ny (B)uv^nw^nx^ny (C)uv^2nwx^2ny (D) All of them Answer: (A) 23) Are the following languages are not context free? (A) Yes (B) No Answer: (A) 24) Which of the following is true ?

(A) (B) (C) (D)

(a) only (b) only (c) only (d) only

Answer: (A)

25) Consider the languages

(A) (a) only (B) (b) only (C) (c) only (D) (d) only Answer(D) 26) A turing machine is a (A)abstract machine (B)hypothetical machine (C)first mathematical model of computer invented by Alan Turing in 1936 (D)All of the above Answer (D) 27) The components of turing machine ---------------------(A) infinite memory tape (B) Tape head (C) Finite control (D) All of the mentioned Answer (D) 28) Which of the functions are performed by the turing machine after reading a symbol? (A) Reads and writes the symbol (B) moves the tape one cell left/right (C) proceeds with next instruction or halts (D) All of them Answer (D) 29) Turing machine can be represented by (A) ID (B) Transition graph (C) Transition table (D) All of the mentioned Answer (D)

30) The turing machine is defined using n-tuples.What is the value of n? (A) 7 (B) 5 (C) 4 (D) None of them Answer (A) 31) Which of the following are the type of Turing machine? (A) Multi tape turing machine (B) Multi track turing machine (C) Register machine (D) All of the mentioned Answer (D) 32) State true or false:Statement: Turing Machine can change symbols on its tape, whereas the FA cannot change symbols on tape. (A) True (B) False Answer (A) 33) State true or false.

(A) Yes (B) No Answer: (A) 34)

(A) (B) (C) (D)

(a) only (b) only (c) only (d) only

Answer(D) 35) Find the Language of given Turing machine

(A) Equal number of a's and b's (B) set of palindromes over a and b (C) Reverse of a string (D) None of the above Answer: (A) 36) Which of the following statements is true? (A) The language is context free it can always be accepted by a deterministic push-down automaton (B) The union of two context free languages is context free (C) The intersection of two context free languages is context free (D) The complement of a context free language is context free Answer: (B) 37) Which one of the following statements is true about languages?

(A) Only L2 is context free (B) Only L2 and L3 are context free (C) Only L1 and L2 are context free (D) All are context free Answer: (D) 38) Which of the following statements is not true about languages?

(A) Push Down Automata (PDA) can be used to recognize L1 and L2 (B) L1 is a regular language (C) All the three languages are context free (D) Turing machine can be used to recognize all the three languages Answer: (C) 39) Let L1, L2 be any two context-free languages and R be any regular language. Then which of the following is/are CORRECT? I. L1∪ L2 is context-free. II. L1’ is context-free. III. L1-R is context-free IV. L1∩L2 is context-free. (A) I,II and IV only (B) I and III only (C) II and IV only (D) I only Answer (B) 40) Which of the following is false about TM (A)It may halt and accept the input (B)It may halt by changing the input (C)It may halt and reject the input (D)It may never halt Answer (B) 41) Consider a Turing machine M to compute f(x) =x+1,which is the correct transition function of M? (Assume x represented by number of 0's. Example x=2 means tape contain 00 ) (Α) δ(q0,0) = (q0,B,R) and δ(q0,B) =(q1,0,R) (B) δ(q0,0)=(q0,0,R) and δ(q0,B) = (q1,0,R) (C) δ(q0,0)=(q0,0,R) and δ(q0,B) = (q1,B,R) (D) None of above Answer ( B) 42) List out the programming techniques used in Turing machine (A) Storage control (B) Checking of symbol (C) Subroutines (D) Multiple tracks Answer :All of above 43) List out applications of turing machine (A) Recognizer of languages (B) Generating devices (C) Computers of functions (D) All of above Answer ( D)

44) How to describe ID of Turing machine? (A) α1qα2 where α1,α2 are left most and rightmost strings in Γ* (B) qα1 where α1 is set of strings in Γ* (C) qx where x is rightmost strings in Γ* (D) None of above Answer ( A) 45) Find the language of given Turing machine

(A) L={strings over 1 containing odd number of 1's} (B) L={strings over 1 containing even number of 1's} (C) L={ set of strings containing 1} (D) None of above Answer (B) 46) Find the transition function of given turing machine

(A) δ(q1,1) = (q2,x,R) , δ(q2,1) =(q1,x,R) and δ(q1,B) = (q3,B,R) (B) δ(q1,1) = (q1,x,R) , δ(q2,1) =(q2,x,R) and δ(q1,B) = (q1,B,R) (C) δ(q1,1) = (q2,x,R) , δ(q2,1) =(q1,x,R) and δ(q1,B) = (q1,B,R) (D) None of above Answer (A) 47) Find the resultant state for 111 and 1111 in TM

(A) q2, q3

(B) q2,q1 (C) q1,q1 (D) None of above Answer (A) 48) Check Is the input 11 accepted by TM ?

(A) Yes (B) No Answer (A) 49) How to define transition function of Turing machine? (A) δ(q,x)=(p,y,D) where q is current state, p is resultant state , x,y are tape symbols and D specify Direction left or Right (B) δ(q,x)=(p,y) where q is current state, p is resultant state , x,y are tape symbols (C) δ(q,x,D)=(p,y) where q is current state, p is resultant state , x,y are tape symbols and D specify Direction left or Right (D) None of above Answer:(A) 50) Define language of Turing machine M. (A) L(M) ={ w/w in Σ* and q0 (B) L(M) ={ w/w in Σ* and q0

α1Pα2 where P is not in F and α1,α2 in Γ* α1Pα2 where P in F and α1,α2 in Γ*

(C) Language accepted by Turing machine called Recursive enumerable languages . (D) Both B and C Answer:(D)...