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

Accepted Answer

A

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

Accepted Answer

1. G is ambiguous because there are strings that can be derived in more than one way. For example, the string "abab" can be derived by applying the rules S -> SS -> S -> ab, S -> ab and also by S -> SS -> ab, S -> ab.2. G produces all strings with an equal number of a's and b's because for every 'a' added by one production, a 'b' is added by another, and vice versa. It also allows for the combination of these pairs in any order, including nesting them within each other.3. G can be accepted by a deterministic PDA because the grammar is context-free. Deterministic PDAs can accept all deterministic context-free languages, and while not all context-free grammars are deterministic, this particular grammar's structure allows for a deterministic PDA to be constructed that accepts it.

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

Accepted Answer

D

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

Accepted Answer

The correct grammar is S->bS|b|aA|bA|a, A->aB|aS, B->bB|aS. This grammar generates all strings in L by starting with the start symbol S and applying the production rules in any order. The production rules ensure that the number of a's in the generated string is always a multiple of 3.

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

Accepted Answer

This is a context-free grammar (CFG) because it has productions of the form V -> w, where V is a single non-terminal and w is a string of terminals and/or non-terminals. This fits the definition of a type-2 grammar in the Chomsky hierarchy.

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}

Accepted Answer

The regular expression (x/y)(x/y) denotes the set of strings that can be formed by choosing either 'x' or 'y' for the first position and either 'x' or 'y' for the second position, resulting in all possible combinations: {xx, xy, yx, yy}.

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*

Accepted Answer

The correct regular expression is 0*1*2* because it allows for any number of 0's (including none) followed by any number of 1's (including none), and then any number of 2's (including none), exactly matching the description.

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.

Accepted Answer

The answer of Suppose that a problem A is known...

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

Accepted Answer

The answer of Which of the following assertions about Turing...

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.

Accepted Answer

A PC not connected to a network is equivalent to a Deterministic Finite-State Automaton (DFA) because it can only be in a finite number of states (e.g., on or off) and its next state is determined by its current state and the input it receives (e.g., a user's command).

Question 11

Recursively enumerable languages are not closed under:
A)Union
B)Intersection
C)Complementation
D)Concatenation

Accepted Answer

Recursively enumerable languages are closed under union, intersection, and concatenation, but they are not closed under complementation. This means that if a language is recursively enumerable, the complement of that language might not be recursively enumerable.

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

Accepted Answer

The complement of a recursive language is recursive, but the complement of a recursively enumerable language that is not recursive is not recursively enumerable.

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

Accepted Answer

R is NP-complete because S is NP-complete and S is polynomial-time reducible to R.

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

Accepted Answer

L is regular because the conditions d(s) mod 5 = 2 and d(s) mod 7 != 4 can be determined by finite automata through state transitions that account for the remainder when divided by 5 and 7, respectively.

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

Accepted Answer

A Turing machine is a finite state machine with a finite tape length without rewinding capability and unidirectional tape movement.

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.

Accepted Answer

Regular languages are a subset of context-free languages, meaning every regular language can be described by a context-free grammar (CFG). This is because regular languages can be generated by regular expressions, and for every regular expression, there exists an equivalent CFG.

Question 17

Recursively enumerable languages are not closed under
A)Complementation
B)Union
C)Intersection
D)None of the above

Accepted Answer

Recursively enumerable languages are closed under union and intersection but not under complementation. This is because while we can construct a Turing machine that recognizes the union or intersection of two recursively enumerable languages, there is no guarantee that the complement of a recursively enumerable language is also recursively enumerable.

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

Accepted Answer

The answer of The following CFG is in
S ? Abb
B...

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

Accepted Answer

PALINDROME and PRIME languages are examples of non-regular languages because they cannot be represented by finite automata or regular expressions. Palindromes require memory to compare characters from the beginning and end of a string, and prime numbers cannot be recognized by a finite state machine due to their infinite non-periodic nature.

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

Accepted Answer

The Pumping Lemma for regular languages states that for any infinite regular language, there exist strings x, y, and z such that any string in the language can be represented as xyz, where the string y can be "pumped" (repeated) any number of times and still produce strings that belong to the language. This property is used to prove whether a language is not regular by showing a contradiction to this lemma.

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

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?

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?

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

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

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

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

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 :

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

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 PC not connected to a network is equivalent to

Recursively enumerable languages are not closed under:

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?

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?

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 FSM can be considered, having finite tape length without rewinding capability and unidirectional tape movement

Which of the following statement is true?

Recursively enumerable languages are not closed under

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

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

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