Have an account?
Skip to Content
Build your own quiz
30 questions
Show Answers
See Preview
- 1. Multiple Choice
Let G be a CFG in Chomsky Normal form (CNF). In order To derive a string of terminals of length n , the number of productions to be used is:
2n + 1
2n - 1
2n
None of these
- 2. Multiple Choice
Recursively enumerable languages are not closed under:
Complementation
Union
Intersection
none of these
- 3. Multiple Choice
Which of the following statement is wrong?
Every recursive language is recursively enumerable.
A language is accepted by FA if and only if it is context free.
Recursive languages are closed under intersection
A language is accepted by FA if and only if it is right linear.
- 4. Multiple Choice
Which of the following is true?
The complement of a recursive language is recursive.
The complement of a recursively enumerable language is recursively enumerable.
The complement of a recursive language is either recursive or recursively enumerable.
The complement of a context-free language is context-free.
- 5. Multiple Choice
If there exists a language L, for which there exists a TM, T,
that accepts every word in L and either rejects or loops for every word that is not in L, is called:
Recursive
Recursively enumerable
NP-HARD
None of these
- 6. Multiple Choice
Universal TM influenced the concept of:
interpretative implementation of programming language.
stored program computers.
computability.
all of these.
- 7. Multiple Choice
Which of the following statements is/are true?
I. Recursive languages are closed under complementation.
II. Recursively enumerable languages are closed under union.
III. Recursively enumerable languages are closed under complementation.
I only
II only
I and II
None of these
- 8. Multiple Choice
Type 0 Grammar is accepted by:
PDA
DFA
LBA
Turing Machine
- 9. Multiple Choice
Which one of the following string(s) is accepted by the above TM?
aabbb
aabbaaaa
abbb
ab
- 10. Multiple Choice
How many derivation trees will be possible for the string w = aabbab for the following CFG.
S ⟶ aB | bA
A ⟶ a | aS | bAA
B ⟶ b | bS | aBB
2
3
4
5
- 11. Multiple Choice
A turing machine that is able to simulate other turing machines:
Nested Turing machines
Universal Turing machine
Counter machine
None of the mentioned
- 12. Multiple Choice
Which of the problems are unsolvable?
Halting problem
Boolean Satisfiability problem
Both (a) and (b)
None of the mentioned
- 13. Multiple Choice
Which of the following a turing machine does not consist of?
input tape
head
state register
none of the mentioned
- 14. Multiple Choice
The value of n if turing machine is defined using n-tuples:
6
7
8
5
- 15. Multiple Choice
If d is not defined on the current state and the current tape symbol, then the machine ______
does not halts
halts
goes into loop forever
none of the mentioned
- 16. Multiple Choice
Statement: Instantaneous descriptions can be designed for a Turing machine. State true or false:
True
False
- 17. Multiple Choice
Which of the following are the models equivalent to Turing machine?
Multi tape turing machine
Multi track turing machine
Turing machine with stay option
All of the mentioned
- 18. Multiple Choice
A language L is said to be ____________ if there is a turing machine M such that L(M)=L and M halts at every point.
Turing acceptable
decidable
undecidable
none of the mentioned
- 19. Multiple Choice
The language accepted by a turing machine is called ____________
Recursive Ennumerable
Recursive
Both (a) and (b)
None of the mentioned
- 20. Multiple Choice
Decidable can be taken as a synonym to:
non recursive
recognizable
recursive
none of the mentioned
- 21. Multiple Choice
The problems which have no algorithm, regardless of whether or not they are accepted by a turing machine that fails to halts on some input are referred as:
Decidable
Undecidable
Computable
None of the mentioned
- 22. Multiple Choice
An algorithm is called efficient if it runs in ____________ time on a serial computer.
polynomial
non polynomial
logarithmic
none of the mentioned
- 23. Multiple Choice
Recursive languages are also known as:
undecidable
decidable
sometimes decidable
none of the mentioned
- 24. Multiple Choice
Which of the following statements is/are FALSE?
1. For every non-deterministic Turing machine,
there exists an equivalent deterministic Turing machine.
2. Turing recognizable languages are closed under union
and complementation.
3. Turing decidable languages are closed under intersection
and complementation.
4. Turing recognizable languages are closed under union
and intersection.
1 and 4 only
2 only
1 and 3 only
3 and 4 only
- 25. Multiple Choice
Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?
(A) L2 – L1 is recursively enumerable.
(B) L1 – L3 is recursively enumerable
(C) L2 ∩ L1 is recursively enumerable
(D) L2 ∪ L1 is recursively enumerable
A
B
C
D
- 26. Multiple Choice
Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE?
L1' --> Complement of L1
L2' --> Complement of L2
L1' is recursive and L2' is recursively enumerable
L1' is recursive and L2' is not recursively enumerable
L1' and L2' are recursively enumerable
L1' is recursively enumerable and L2' is recursive
- 27. Multiple Choice
Which among the following is the format of unit production?
B->Aa
A->b
A->B
None of the mentioned
- 28. Multiple Choice
Given grammar:
S->aA
A->a
A->B
B-> A
B->bb
Which of the following is the production of B after simplification by removal of unit productions?
A
bb
aA
A| bb
- 29. Multiple Choice
Given grammar G:
S-> ABA, A->aA|e, B-> bB|e
Eliminate e and unit productions. State the number of productions the starting variable holds?
6
7
9
8
- 30. Multiple Choice
Given grammar G:
S-> A| B| C
A-> aAa| B
B-> bB|bb
C->aCaa|D
D->baD|abD|aa
Eliminate e and unit productions and state the number of variables left?
4
5
8
7
- Answer choicesTagsAnswer choicesTags