1. A language L is said to be Turing decidable if:
a) recursive
b) TM recognizes L
c) TM accepts L
d) None of the mentioned
View Answer
Explanation: A language L is recursively ennumerable if there is a turing machine that accepts L, and recursive if there is a TM that recognizes L.(Sometimes these languages are alse called Turing-acceptable and Turing-decidable respectively).
2. State true or false:
Statement: The operations of PDA never work on elements, other than the top.
a) true
b) false
View Answer
Explanation: The term pushdown refers to the fact that the elements are pushed down in the stack and as per the LIFO principle, the operation is always performed on the top element of the stack.
a) Human Readable/ Machine Readable
b) Extended from SGML
c) Developed by www consortium
d) All of the mentioned
View Answer
Explanation: XML is an open format markup language with a filename extension of .xml.
4. A pushdown automata can be defined as: (Q, ?, G, q0, z0, A, d)
What does the symbol z0 represents?
a) an element of G
b) initial stack symbol
c) top stack alphabet
d) all of the mentioned
View Answer
Explanation: z0 is the initial stack symbol, is an element of G. Other symbols like d represents the transition function of the machine.
5. Which of the following automata takes stack as auxiliary storage?
a) Finite automata
b) Push down automata
c) Turing machine
d) All of the mentioned
View Answer
Explanation: Pushdown Automaton uses stack as an auxiliary storage for its operations. Turing machines use Queue for the same.
6. A language that admits only ambiguous grammar:
a) Inherent Ambiguous language
b) Inherent Unambiguous language
c) Context free language
d) Context Sensitive language
View Answer
Explanation: A context free language for which no unambiguous grammar exists, is called Inherent ambiguous language.
7. State true or false:
Statement: Every context free grammar can be transformed into an equvalent non deterministic push down automata.
a) true
b) false
View Answer
Explanation: Push down automata is the automaton machine for all the context free grammar or Type 2 languages.
a(aUb)*b
a) (1) S ? aMb
(2) M ? e
(3) M ? aM
(4) M ? bM
b) (1) S ? aMb
(2) M ? Mab
(3) M ? aM
(4) M ? bM
c) (1) S ? aMb
(2) M ? e
(3) M ? aMb
(4) M ? bMa
d) None of the mentioned
View Answer
Explanation:
The basic idea of grammar formalisms is to capture the structure of string by
a) using special symbols to stand for substrings of a particular structure
b) using rules to specify how the substrings are combined to form new substrings.
9. Which of the following is a simulator for non deterministic automata?
a) JFLAP
b) Gedit
c) FAUTO
d) None of the mentioned
View Answer
Explanation: JFLAP is a software for experimenting with formal topics including NFA, NPDA, multi-tape turing machines and L-systems.
10. State true or false:
Statement: Every context free language can be generated by a grammar which contains no useless non terminals.
a) true
b) false
View Answer
Explanation: At first, we detect useless symbols and discard them. Inorder to find whether a symbol is useless, just make it the starting symbol and check for emptiness.
a) A->B
b) A->b
c) B->Aa
d) None of the mentioned
View Answer
Explanation: Any production of the format A-> B where A and B belongs to the V set, is called Unit production.
a) Lexical Analyser
b) BOT
c) State charts
d) None of the mentioned
View Answer
Explanation: Finite state automation is used in Lexical Analyser, Computer BOT (used in games), State charts, etc.
13. Let f: N->N be a step counting function. Then for some constant C, Time(f) is a proper subset of Time(_______)
a) O(nf)
b) O(n+f)
c) O(n2f2)
d) None of the mentioned
View Answer
Explanation: Using the encoding function, it is possible to show that if the function f is a step counting function, then the function Cn2(f(n))2 is the total number of moves required.
a) Las Vegas Algorithm
b) Monte Carlo Algorithm
c) Atlantic City Algorithm
d) All of the mentioned
View Answer
Explanation: The atlantic city algorithms which are bounded polynomial time algorithms are probably correct and probably fast. It is correct more than 75% of the times.
a) time
b) space
c) both time and space
d) none of the mentioned
View Answer
Explanation: Though it may use extra time, but as PSPACE=NPSPACE from savitch’s theorem, we can say that space taken is same for both the machins, deterministic as well as non-deterministic.
