amazon

shopclues

myntra

Home / MCQ Computer Science / Automata Theory Multiple Choice Quaestion & Answers (MCQs) set-41

Automata Theory Multiple Choice Quaestion & Answers (MCQs) set-41

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

View Answer

Answer: a,b
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

View Answer

Answer: a
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.

3. Which among the following are true for an Extensible markup language?
a) Human Readable/ Machine Readable
b) Extended from SGML
c) Developed by www consortium
d) All of the mentioned

View Answer

View Answer

Answer: d
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

View Answer

Answer: d
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

View Answer

Answer: b
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

View Answer

Answer: a
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

View Answer

Answer: a
Explanation: Push down automata is the automaton machine for all the context free grammar or Type 2 languages.

8. Which of the following is the correct representation of grammar for the given regular expression?
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

View Answer

Answer: a
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

View Answer

Answer: a
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

View Answer

Answer: a
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.

11. Which among the following is the format of unit production?
a) A->B
b) A->b
c) B->Aa
d) None of the mentioned

View Answer

View Answer

Answer: a
Explanation: Any production of the format A-> B where A and B belongs to the V set, is called Unit production.

12. Which among the following is not an application of FSM?
a) Lexical Analyser
b) BOT
c) State charts
d) None of the mentioned

View Answer

View Answer

Answer: d
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

View Answer

Answer: c
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.

14. Which of the following algorithms are probably correct as well as fast?
a) Las Vegas Algorithm
b) Monte Carlo Algorithm
c) Atlantic City Algorithm
d) All of the mentioned

View Answer

View Answer

Answer: c
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.

15. Without needing extra __________ we can simulate non deterministic turing machine using deterministic turing machine.
a) time
b) space
c) both time and space
d) none of the mentioned

View Answer

View Answer

Answer: b
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.

Check Also

Automata Theory Multiple Choice Quaestion & Answers (MCQs) set-47

1. A DTD is associated with a XML file by means of ___________ a) Function …

Leave a Reply

Your email address will not be published. Required fields are marked *

error: Content is protected !!