TOC(CS8501) UNIT1 MCQ - Multi Choice Questions and Answers for UNIT 1 PDF

Preview

Summary

Multi Choice Questions and Answers for UNIT 1 ...

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 I - AUTOMATA FUNDAMENTALS 1) What is the use of Automata theory (A) It is the study of abstract computing devices or machines and the study of the limits of computation. (B) The usefull model for many kinds of software and hardware. (C) Software for designing and checking behaviour of digital circuits. (D) All of the above Answer : D 2) Find the applications of Automata. (A) lexical analyzer of a typical compiler (B) Software for scanning large bodies of text such as collection of web pages (C) Software for verifying systems of all types that have finite number of states such as communication protocols (D) All of above Answer : D 3) List out important notations or structural representation of automata (A) Grammars (B) Regular expressions (C) Both of above (D) None of the mentioned Answer: C 4) Find the way of proving sentence. (A) Deductive proof (B) Inductive Proof (C) Proof by contradiction and Proof by counterexample (D) All of above Answer: D 5) The statement of the form “A if and only if B” is equivalent to -------------(A) A iff B (B) A is equivalent to B (C) A exactly when B (D) All of above Answer: D 6) The contrapositive of the statement “if H then C” is ................ (A) If C then H (B) If not H then not C (C) If not C then not H (D) If not H then C Answer: C

7) Using proof by contradiction. To prove the statement of form If H then C by ----------(A) If not H then not C (B) H and not C imp;ies falsehood or If H and not C then false H (C) If not C then not H (D) If not H then C Answer :B 8) Which statement is false about Inductive proof (A) Inductive proof deal with integers and recursively defined objects (B) It has two steps: Basis and Inductive step (C) Inductive step shows if s(n) then s(n+1) (D) None of the Above Answer: D 9) What is deductive proof? (A) A proof proceeds by listing statements that are either given to be true or follow logically from the previous statements. (B) Begin with Hypothesis and prove conclusion from the hypthosis and previous statements (C) Both of Above (D) None of above Answer: C 10) Which statement is false about the following definition of terms (A) Alphabet is a finite non empty set of symbols (B) String is a finite sequence of symbols chosen from some alphabet (C) Language is a set of strings all of which symbols choosen from alphabet (D) None of the above Answer: D 11) Which are the components of Finite Automata (A) Input tape contains single string; (B) Tape head reads input string one symbol at a time (C) Finite Control or Memory is in one of a finite number of states. (D) All of above Answer: (D) 12) Define Finite Automata (A) Finite automata is defined by M=(Q, ∑,δ, q0, F) where Q- set of states, ∑ −set of input symbols, δ – transition function , q0- starting state , F as set of final states. (B) Finite automata contain finite set of states and finite set of input symbols (C) Both of above (D) None of Above Answer: (C) 13) List out types of Finite state system (A) Deterministic Finite Automata and NonDeterminstic Finite Automata (B) Moore Machine and Mealy Machine (C) Both of above (D) None of them Answer:(C)

14) Which is false about transition function in deterministic finite automata. (A) Transition function determines how state changes each time input symbol is processed. (B) It take argument as state and a input symbol and return a state ie. Q× ∑→ Q. (C) If q is a state,a is an input symbol and p is the resultant state then transition function is denoted by δ (q,a)=p (D)Transition function specify the set of states in finite automata. Answer: (D) 15) Finite automata requires minimum _______ number of stacks. (A) 1 (B) 0 (C) 2 (D) None of the mentioned Answer:(B) 16) Language of finite automata is. (A) Type 0 (B) Type 1 (C) Type 2 (D) Type 3 Answer :(A) 17) Languages of a automata is (A) If it is accepted by automata (B) If it halts (C) If automata touch final state in its life time (D) All language are language of automata Answer: (A) 18) NDFA Stands for____________________________ (A) Non Determining Finite Automata (B) None Deterministic Finite Automata (C) Non Deterministic First Automata (D) Non Deterministic Finite Automata Answer: D 19) Find the final state for 101001 and 11101 from the finite automata

(A) A,B (B) C,A (C) C,B (D) C,C Answer: (B)

20) How to represent finite automata? (A) Transition diagram or Transition graph (B) Transition table (C) Both of above (D) None of above Answer (C) 21) Find the language of finite automata

(A) L={set of strings of 0's and 1's} (B) L={ set of strings of 0's and 1's ending with 1} (C) L={ set of strings of 0's and 1's with odd number of 1's} (D) L={ set of strings of 0's and 1's with even number of 1's} Answer (C) 22) In finite automata, Find the minimum number of states required to accept string end with 101. (A) 4 (B) 3 (C) 2 (D) can't be represented Answer : (A) 23) Consider the following DFA, It accepts strings of 0'1 and 1's with -----------------.

(A) substring 01 (B) ends with 01 (C) start with 01 (D) None of them Answer: (A) 24) Which is false about Language of DFA L? (A) L is a regular language (B) L is defined by regular grammar (C) L ={ w | δˆ(q0,w) is in F} (D) L is a Context free language. Answer : (D) 25) Is it language of NFA L ={ w | δˆ(q0,w) ∩ F ≠ ∅} ? (A) Yes (B) No Answer: (A)

26) Find the transition table for the following finite automata

(A) δ

0

1

->q0

q2

q0

q1

q1

q1

q2

q2

q1

δ

0

1

->q0

q2

q0

q1

q1

q1

q2

q2

q2

0

1

->q0

q2

q0

q1

q1

q2

q2

q2

q2

0

1

->q0

q2

q2

q1

q1

q1

q2

q2

q2

B)

C) δ

D) δ

Answer :(A) 27) Find the language of NFA

(A) L={set of strings of 0's and 1's} (B) L={ set of strings of 0's and 1's ending with 01} (C) L={ set of strings of 0's and 1's with odd number of 1's} (D) L={ set of strings of 0's and 1's with starting with 01} Answer: (B)

28) Check input 00101 is accepted by the following finite automata.

(A) Yes (B) No Answer: (A) 29) Consider a nondeterministic finite automata. Find the resultant state for 00101?

(A) {q0,q2} (B) {q0,q1} (C) {qo,q1,q2} (D) None of the above Answer: (A) 30) Construct DFA for the following NFA. Find the resultant states in DFA

(A) {q0},{q0,q1},{q0,q1,q2} (B) {q0},{q0,q1},{q0,q2} (C) {q0,q2},{q0,q1},{q0,q1,q2} (D) None of above Answer: (B) 31) State true or false about statement “ A language L is accepted by some DFA if and only if l is accepted by NFA” (A) True (B) False Answer: (A) 32) Let n be the number of states in NFA then there exists a DFA with minimum number of states ----------(A) n2 (B) nn+1 (C) 2n (D) 2n+1 Answer:(C)

33) Which is true about comparision of NFA and DFA (A) NFA and DFA have equal number of states for the same regular language . (B) NFA allow more than one transition for input symbol from state but DFA allow only one transition. (C) NFA is more powerfull than DFA. (D) All of the above mentioned Answer:(B) 34) Convert the following NFA to DFA and find the number of states in DFA.

(A) 5 (B) 6 (C) 7 (D) 8 Answer: (D ) 35) An Automata which allows transformation to new state without consuming any input symbol is called (A) NFA (B) DFA (C) ∈−NFA (D) None of above Answer:(C) 36) For ∈ −NFA, which among the following are correct? (A) δ : Q× ∑→ Q (B) δ : Q× ∑→ 2Q (C) δ : Q× (∑ ∪ {ε}) → 2Q (D) All of them Answer:(C) 37) What is ∈ −closure of a state q0? (A) ∈--closure(q0 ) denotes a set of all vertices p such that there is a path from q0 to p labeled ∈. (B) It contain state q0 and set of states reachable from qo along the path labelled ∈ (C) Both of above (D) None of them Answer:(C)

38) According to given transitions,which among the following are the epsilon closures of q1 for the following NFA .

(A) {q0,q1,q2} (B) {q1,q2} (C) {q2} (D) None of the above Answer:(B) 39) Let δ denote the transition function and δˆ denote the extended transition function of the ∈ −NFA whose transition table is given below: GATE 2017 δ

∈

a

b

->q0

q2

q1

q0

q1

q0

ϕ

ϕ

q2

ϕ

ϕ

q2

then δˆ(q2,aba) is (A) ϕ (B) {q0, q1, q3} (C) {q0, q1, q2} (D) {q0, q2, q3} Answer (C)

40) The above DFA accepts the set of all strings over {0,1} that

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

begin either with 0 or 1. end with 0 end with 00. contain the substring 00.

Answer(C)

41) The finite automata is called NFA then there exists -------------- for a specific input from current state to next state. (A) Single path (B) Multiple path (C) Only two paths (A) None of above Answer(B) 42) Which of the following are example of finite state system? (A) Contol mechanishm of elevator,traffic lights, etc (B) Combinational logic (C) Both a and B (D) Digital Watch Answer (C) 43) E-close of state is a combination of self state and -------------(A) reachable state (B) initial state (C) Final state (D) ε-reachable state Answer (D) 44) Find the regular expression for E-NFA

(A) a+aa*b+a*b (B) a+aa*b+b*a (C) a+a*b+b (D) None of above Answer (A) 45) Can a DFA simulate NDFA (A) Yes (B) No (C) Sometimes (D) Depends on NDFA Answer: (A) 46) Find the wrong statement? (A) The language accepted by NFA are the languages accepted by DFA (B) the language accepted by E-NFA are the languages accepted by NFA (C) For a regular expression r, there does not exist NFA with L(r) any transit that accept (D) None of these Answer: (C) 47) The behaviour of a NFA can be stimulated by DFA (A) Always (B) Sometimes (C) Never (D) Depends on NFA Answer: (A)

48) The relation between NFA-accepted languages and DFA accepted languages is (A) Equal (B) More powerful (C) less powerful (D) subset of DFA Answer: (A) 49) Find the language of DFA

(A) L={ set of strings 0's and 1's start with 00} (B) L={ set of strings 0's and 1's end with 0} (C) L= { set of strings 0's and 1's with alternating 0's and 1's } (D) L= { et of strings 0's and 1's with start and end with same string} Answer: (A) 50) Find the language of Deterministic finite automata

(A) L={ set of strings 0's and 1's start with 00} (B) L={ set of strings 0's and 1's end with 0} (C) L= { set of strings 0's and 1's with alternating 0's and 1's } (D) L= { et of strings 0's and 1's with start and end with same string} Answer: (D)...