1. A DTD is associated with a XML file by means of ___________
a) Function
b) <!DOCTYPE>
c) Macros
d) None of the mentioned
View Answer
Explanation: A document type definition defines the legal building blocks of an XML document .
a) Embedded PDA
b) Nested Stack automata
c) DPDA
d) Counter Automaton
View Answer
Explanation: This class of automata can recognize a set of context free languages like {anbn|n belongs to N}
3. A null production can be referred to as:
a) String
b) Symbol
c) Word
d) All of the mentioned
View Answer
Explanation: Null production is always taken as a string in computational theory.
4. Which of the following can be accepted by a DPDA?
a) The set of even length palindrome over {a,b}
b) The set of odd length palindrome over {a,b}
c) {xxc| where c stands for the complement,{0,1}}
d) None of the mentioned
View Answer
Explanation: Theorem: The language pal of palindromes over the alphabet {0,1} cannot be accepted by any finite automaton , and it is therefore not regular.
5. Find a regular expression for a grammar which generates a language which states :
L contains a set of strings starting wth an a and ending with a b, with something in the middle.
a) a(a*Ub*)b
b) a*(aUb)b*
c) a(a*b*)b
d) None of the mentioned
View Answer
Explanation: The grammar for the same language can be stated as :
(1) S ? aMb
(2) M ? A
(3) M ? B
(4) A ? e
(5) A ? aA
(6) B ? e
(7) B ? bB
6. Let G=(V, T, P, S)
where a production can be written as:
S->aAS|a
A->SbA|ba|SS
Which of the following string is produced by the grammar?
a) aabbaab
b) aabbaa
c) baabab
d) None of the mentioned
View Answer
Explanation: The step wise grammar translation can be written as:
aAS->aSbaA->aabAS->aabbaa
7. Given:
S->aSb
S->e
S-> A
A->aA
B->C
C->D
The ratio of number of useless variables to number of useless production is:
a) 1
b) 3/4
c) 2/3
d) 0
View Answer
Explanation: A, B, C, D are the useless symbols in the given grammar as they never tend to lead to a terminal. The productions S-> A, A->aA, B->C, C->D are also termed as useless production as they will never produce a string to the grammar.
8. 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?
a) 6
b) 7
c) 9
d) 5
View Answer
Explanation: After reduction the grammar looks like:
S->ABA| AB| BA| AA| Aa| a| bB| b
A->aA| a
B->bB| b
9. Which of the following cannot be filled in the blank below?
Statement: There are CFLs L1 nad L2 so that ___________is not a CFL.
a) L1nL2
b) L1′
c) L1*
d) None of the mentioned
View Answer
Explanation: A set of context free language is closed under the following operations:
a) Union
b) Concatenation
c) Kleene
10. Which among the following can parse a context free grammar?
a) top down parser
b) bottom up parser
c) CYK algorithm
d) all of the mentioned
View Answer
Explanation: We use certain algorithms to parse a context free grammar which include the most popular CYK algorithm which employs the concept of bottom up parsing and dynamic parsing.
11. Which of the following are valid membership algorithms?
a) CYK algorithm
b) Exhaustive search parser
c) Both (a) and (b)
d) None of the mentioned
View Answer
Explanation: CYK algorithm is a parsing algorithm for context free grammars, which employs bottom up parsing and dynamic programming.
12. The ability for a system of instructions to simulate a Turing Machine is called _________
a) Turing Completeness
b) Simulation
c) Turing Halting
d) None of the mentioned
View Answer
Explanation: Turing Completeness the ability for a system of instructions to simulate a Turing machine. A programming language that is Turing complete is theoretically capable of expressing all tasks accomplishable by computers; nearly all programming languages are Turing complete.
13. Which among the following is incorrect for o-machines?
a) Oracle Turing machines
b) Can be used to study decision problems
c) Visualizes Turing machine with a black box which is able to decide cerain decion problems in one operation
d) None of the mentioned
View Answer
Explanation: In automata theory, an o- machine or oracle machine is a abstract machine used to study decision problems. The problem the oracle solves can be of any complexity class. Even undecidable problems like halting problems can be used.
14. If L is a recursive language, L’ is:
a) Recursive
b) Recursively Ennumerable
c) Both (a) and (b)
d) None of the mentioned
View Answer
Explanation: If T is a turing machine recognizing L, we can make it recognize L’ by interchanging the two outputs. And every recursive language is recursively ennumerable.
15. Which of the following statements are false?
a) A multi track turing machine is a special kind of multi tape turing machine
b) 4-heads move independently along 4-tracks in standard 4-tape turing machine
c) In a n-track turing machine, n head reads and writes on all the tracks simultaneously.
d) All of the mentioned
View Answer
Explanation: In a n-track turing machine, one head reads and writes on all the tracks simultaneously.
