1. XML is a _________ markup language.
a) meta
b) beta
c) octa
d) peta
View Answer
Explanation: Generally speaking, a meta language is a language used to describe a language. XML is a metalanguage that is used to describe a markup language.
2. Which of the following are always unambiguous?
a) Deterministic Context free grammars
b) Non-Deterministic Regular grammars
c) Context sensitive grammar
d) None of the mentioned
View Answer
Explanation: Deterministic CFGs are always unambiguous , and are an important subclass of unambiguous CFGs; there are non-deterministic unambiguous CFGs, however.
3. Which of the following allows stacked values to be sub-stacks rather than just finite symbols?
a) Push Down Automaton
b) Turing Machine
c) Nested Stack Automaton
d) None of the mentioned
View Answer
Explanation: In computational theory, a nested stack automaton is a finite automaton which makes use of stack containing data which can be additional stacks.
4. The closure property of context free grammar includes :
a) Kleene
b) Concatenation
c) Union
d) All of the mentioned
View Answer
Explanation: Context free grammars are closed under kleene operation, union and concatenation too.
5. Which of the following correctly recognize the symbol ‘|-‘ in context to PDA?
a) Moves
b) transition function
c) or/not symbol
d) none of the mentioned
View Answer
Explanation: Using this notation, we can define moves and further acceptance of a string by the machine.
6. A push down automata can represented using:
a) Transition graph
b) Transition table
c) ID
d) All of the mentioned
View Answer
Explanation: Yes, a PDA can be represented using a transition diagram, transition table and an instantaneous description.
7. If the PDA does not stop on an accepting state and the stack is not empty, the string is:
a) rejected
b) goes into loop forever
c) both (a) and (b)
d) none of the mentioned
View Answer
Explanation: To accept a string, PDA needs to halt at an accepting state and with a stack empty, else it is called rejected. Given a PDA M, we can construct a PDA M’ that accepts the same language as M, by both acceptance criteria.
8. Which of the following strings is not generated by the given grammar:
S->SaSbS|e
a) aabb
b) abab
c) abaabb
d) None of the mentioned
View Answer
Explanation: All the given options are generated by the given grammar. Using the methods of left and right derivations, it is simpler to look for string which a grammar can generate.
9. A CFG consist of the following elements:
a) a set of terminal symbols
b) a set of non terminal symbols
c) a set of productions
d) all of the mentioned
View Answer
Explanation: A CFG consists of:
a) a set of terminals, which are characters of alphabets that appear in the string generated by the grammar.
b) a set of non terminals, which are placeholders for patterns of terminal symbols that can be generated by the nonterminal symbols.
c) a set of productions, which are set of rules to transit from one state to other forming up the string
d) a start symbol, a special non terminal symbol that appears in the initial string generated in the grammar.
10. L->rLt|tLr|t|r
The given grammar produces a language which is:
a) All palindrome
b) All even palindromes
c) All odd palindromes
d) Strings with same begin and end symbols
View Answer
Explanation: As there exists no production for the palindrome set, even palindromes like abba, aabbaa, baaaaaab, etc will not be generated
11. Suppose A->xBz and B->y, then the simplified grammar would be:
a) A->xyz
b) A->xBz|xyz
c) A->xBz|B|y
d) none of the mentioned
View Answer
Explanation: For the first step, substitute B in first production as it only produces terminal and remove B production as it has already been utilized.
We get A->xBz|xyz and now, as B has no production, we eliminate the terms which hold the variable B, thus the answer remain A->xyz.
12. In context to the process of removing useless symbols, which of the following is correct?
a) We remove the Nullable variables
b) We eliminate the unit productions
c) We eliminate products which yield no terminals
d) All of the mentioned
View Answer
Explanation: In the process of removal of useless symbols, we want to remove productions that can never take part in any derivation.
13. Statement:
For A-> e ,A can be erased. So whenever it appears on the left side of a production, replace with another production without the A.
State true or false:
a) true
b) false
View Answer
Explanation: A can be erased. So whenever it appears on the right side of the production, replace with another production without the A.
14. If grammar G is unambiguous, G’ produced after the removal of Unit production will be:
a) ambiguous
b) unambiguous
c) finite
d) cannot be said
View Answer
Explanation: With the simplification of Context free grammars, undesirable properties are introduced. It says, if grammar G, before simplification is unambiguous, after simplification will also be unambiguous.
15. Given grammar G:
(1)S->AS
(2)S->AAS
(3)A->SA
(4)A->aa
Which of the following productions denies the format of Chomsky Normal Form?
a) 2,4
b) 1,3
c) 1, 2, 3, 4
d) 2, 3, 4
View Answer
Explanation: The correct format: A->BC, A->a, X->e.
