NEW
Font size
WorksheetsTAFL Quiz-3 (Module-2)
Total questions: 30
Worksheet time: 15mins
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
Recursively enumerable languages are not closed under:
Complementation
Union
Intersection
none of these
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.
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.
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
Universal TM influenced the concept of:
interpretative implementation of programming language.
stored program computers.
computability.
all of these.
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
Type 0 Grammar is accepted by:
PDA
DFA
LBA
Turing Machine
Which one of the following string(s) is accepted by the above TM?
aabbb
aabbaaaa
abbb
ab
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
A turing machine that is able to simulate other turing machines:
Nested Turing machines
Universal Turing machine
Counter machine
None of the mentioned
Which of the problems are unsolvable?
Halting problem
Boolean Satisfiability problem
Both (a) and (b)
None of the mentioned
Which of the following a turing machine does not consist of?
input tape
head
state register
none of the mentioned
The value of n if turing machine is defined using n-tuples:
6
7
8
5
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
Statement: Instantaneous descriptions can be designed for a Turing machine. State true or false:
True
False
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
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
The language accepted by a turing machine is called ____________
Recursive Ennumerable
Recursive
Both (a) and (b)
None of the mentioned
Decidable can be taken as a synonym to:
non recursive
recognizable
recursive
none of the mentioned
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
An algorithm is called efficient if it runs in ____________ time on a serial computer.
polynomial
non polynomial
logarithmic
none of the mentioned
Recursive languages are also known as:
undecidable
decidable
sometimes decidable
none of the mentioned
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
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
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
Which among the following is the format of unit production?
B->Aa
A->b
A->B
None of the mentioned
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
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
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
