Deck 3: Computational Theory : Grammar, Language, and Complexity

Question 1

Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G =(V,E)with divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?

A)Both DHAM3 and SHAM3 are NP-hard
B)SHAM3 is NP-hard, but DHAM3 is not
C)DHAM3 is NP-hard, but SHAM3 is not
D)Neither DHAM3 nor SHAM3 is NP-hard

Answer 1

Both DHAM3 and SHAM3 are NP-hard

Question 2

Consider the following statements about the context free grammar G = {S - >SS,S - >ab,S ->ba, S - ?}
I. G is ambiguous
II. G produces all strings with equal number of a's and b's
III. G can be accepted by a deterministic PDA.
Which combination below expresses all the true statements about G?

A)1 only
B)1 and 3
C)2 and 3
D)1,2 and 3

Answer 2

1,2 and 3

Question 3

Consider the regular language L =(111+11111)*. The minimum number of states in any DFA accepting this languages is:

A)3
B)5
C)8
D)9

Answer 3

9

Question 4

Give a production grammar for the language L = {x/x ? (a,b)*, the number of a's in x is multiple of 3}.

A){S->bS,S->b,S->aA,S->bA,A->aB,B->bB,B->aS,S->a}
B){S->aS,S->bA,A->bB,B->bBa,B->bB}
C){S->aaS,S->bbA,A->bB,B->ba}
D)None of the above

Question 5

The production Grammar is {S->aSbb,S->abb} is

A)type-3 grammar
B)type-2 grammar
C)type-1 grammar
D)type-0 grammar

Question 6

Regular expression (x/y)(x/y) denotes the set

A){xy,xy}
B){xx,xy,yx,yy}
C){x,y}
D){x,y,xy}

Question 7

The regular expression have all strings in which any number of 0's is followed by any number of 1's followed by any number of 2's is :

A)(0+1+2)*
B)0*1*2*
C)0* + 1 + 2
D)(0+1)*2*

Question 8

Suppose that a problem A is known to have a polynomial-time verification algorithm. Which of the following statements can be deduced.

A)A is in NP.
B)A is in NP but not P
C)A is in both NP and P.
D)A is NP-complete.

Question 9

Which of the following assertions about Turing Machines is true? Blank symbol(s) may occur in the input. At any stage of a computation, there are only finitely many non-blank Symbols on the tape.

A)Assertions (a) and (b) are both true.
B)Neither (a) nor (b) is true.
C)Both False
D)None of above

Question 10

A PC not connected to a network is equivalent to

A)A Deterministic Finite-State Automaton,
B)A Turing Machine,
C)A Push-Down Automaton,
D)None of the above.

Question 11

Recursively enumerable languages are not closed under:

A)Union
B)Intersection
C)Complementation
D)Concatenation

Question 12

Let L₁ be a recursive language, and let L₂ be a recursively enumerable but not a recursive language. Which one of the following is TRUE?

A)( L₁)' is recursive and (L₂)' is recursively enumerable
B)( L₁)' is recursive and (L₂)' is not recursively enumerable
C)( L₁)' and (L₂)' are recursively enumerable
D)( L₁)' is recursively enumerable and (L₂)' is recursive

Question 13

Let S be an NP-complete problem, Q and R be two other problems not known to be in NP. Q is polynomial-time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true?

A)R is NP-complete
B)R is NP-hard
C)Q is NP-complete
D)Q is NP-hard

Question 14

For s ? (0+1)* let d(s) denote the decimal value of s(e.g.d(101)) = 5 Let L = {s ? (0+1)* d(s) mod 5=2 and d(s) mod 7 != 4} Which one of the following statements is true?

A)L is recursively enumerable, but not recursive
B)L is recursive, but not context-free
C)L is context-free, but not regular
D)L is regular

Question 15

A FSM can be considered, having finite tape length without rewinding capability and unidirectional tape movement

A)Turing machine
B)Pushdown automata
C)Context free languages
D)Regular languages

Question 16

Which of the following statement is true?

A)All languages can be generated by CFG
B)The number of symbols necessary to simulate a Turing Machine(TM) with m symbols and n states is mn.
C)Any regular languages have an equivalent CFG.
D)The class of CFG is not closed under union.

Question 17

Recursively enumerable languages are not closed under

A)Complementation
B)Union
C)Intersection
D)None of the above

Question 18

The following CFG is in
S ? Abb
B ? bAA
A ? a
B ? b

A)Chomsky normal form but not strong Chomsky normal form
B)Weak Chomsky normal form but not Chomsky normal form
C)Strong Chomsky normal form
D)Greibach normal form

Question 19

The languages -------------- are the examples of non regular languages.

A)PALINDROME and PRIME
B)PALINDROME and EVEN-EVEN
C)EVEN-EVEN and PRIME
D)FACTORIAL and SQURE

Question 20

Let L be any infinite regular language, defined over an alphabet ? then there exist three strings x, y and z belonging to ? such that all the strings of the form XY^ n Z for n=1,2,3, … are the words in L called

A)Complement of L
B)Pumping Lemma
C)Kleene's theorem
D)None in given

Question 21

Languages are proved to be regular or non regular using pumping lemma.

A)True
B)False
C)Not always true
D)can't say anything

Question 22

___________ states are called the halt states.

A)ACCEPT and REJECT
B)ACCEPT and READ
C)ACCEPT AND START
D)ACCEPT AND WRITE

Question 23

The part of an FA, where the input string is placed before it is run, is called _______

A)State
B)Transition
C)Input Tape
D)Output Tape

Question 24

The PDA is called non-deterministic PDA when there are more than one out going edges from……… state

A)START or READ
B)POP or REJECT
C)READ or POP
D)PUSH or POP

Question 25

If an effectively solvable problem has answered in yes or no, then this solution is called

A)Decision procedure
B)Decision method
C)Decision problem
D)Decision making