Uncategorized

# Automata Theory Multiple Choice Question & Answers (MCQs) set-14

1. Which of the following not an example Bounded Information?
a) fan switch outputs {on, off}
c) colour of the traffic light at the moment
d) none of the mentioned

Explanation: Bounded information refers to one whose output is limited and it cannot be said what were the recorded outputs previously until memorized.
2. According to the 5-tuple representation i.e. FA= {Q, ∑, δ, q, F}
Statement 1: q ϵ Q’; Statement 2: FϵQ
a) Statement 1 is true, Statement 2 is false
b) Statement 1 is false, Statement 2 is true
c) Statement 1 is false, Statement 2 may be true
d) Statement 1 may be true, Statement 2 is false

Explanation: Q is the Finite set of states, whose elements i.e. the states constitute the finite automata.
3. An automaton that presents output based on previous state or current input:
a) Acceptor
b) Classifier
c) Transducer
d) None of the mentioned.

Explanation: A transducer is an automaton that produces an output on the basis of what input has been given currently or previous state.
4. If L1 and L2 are regular languages, which among the following is an exception?
a) L1 U L2
b) L1 – L2
c) L1 ∩ L2
d) All of the mentioned

Explanation: It the closure property of Regular language which lays down the following statement:
If L1, L2 are 2- regular languages, then L1 U L2, L1 ∩ L2, L1C, L1 – L2 are regular language.
5. ε- closure of q1 in the given transition graph:
a) {q1}
b) {q0, q2}
c) {q1, q2}
d) {q0, q1, q2}

Explanation: ε-closure is defined as the set of states being reached through ε-transitions from a starting state.
6. Reverse of a DFA can be formed by
a) using PDA
b) making final state as non-final
c) making final as starting state and starting state as final state
d) None of the mentioned

Explanation: By making final state as starting state string starting from end will be accepted.

7. In order to represent a regular expression, the first step to create the transition diagram is:
a) Create the NFA using Null moves
b) Null moves are not acceptable, thus should not be used
c) Predict the number of states to be used in order to construct the Regular expression
d) None of the mentioned

Explanation: Two steps are to be followed while converting a regular expression into a transition diagram:
a) Construct the NFA using null moves.
b) Remove the null transitions and convert it into its equivalent DFA.
8. The finite automata accept the following languages:
a) Context Free Languages
b) Context Sensitive Languages
c) Regular Languages
d) All the mentioned

Explanation: A finite automaton accepts the languages which are regular and for which a DFA can be constructed.
9. Generate a regular expression for the given language:l
L(x): {xÎ{0,1}*| x ends with 1 nd does not contain a substring 01}
a) (0+01)*
b) (0+01)*1
c) (0+01)*(1+01)
d) All of the mentioned

Explanation: (a) and (b) are the general cases where we restrict the acceptance of a string witrh substring 00 but we ignore the case where the string needs to end with 1 which therby, does not allows the acceptance of e.
10. Consider following regular expression
i) (a/b)* ii) (a*/b*)* iii) ((ϵ/a)b*)*
Which of the following statements is correct
a) i,ii are equal and ii,iii are not
b) i,ii are equal and i,iii are not
c) ii,iii are equal and i,ii are not
d) all are equal

Explanation : All are equivalent to (a+b)*.
11. A symbol X is ________ if there exists : S->* aXb
a) reachable
b) generating
c) context free
d) none of the mentioned

Explanation: A symbol X is generating if there exists : X->*w for some w that belongs to T*.
Also, a symbol can never be context free.
12. YACC is an acronym for:
a) Yes Another Compile Compiler
b) Yet Another Compile Compiler
c) Yet Another Compiler Compiler
d) Yes Another Compiler Compiler

Explanation: YACC stands for ‘Yet another compiler compiler’ and it was developed by Stephen Johnson in B programming language later translated to C.
13. Which of the following is incorrect for HTML5 markup construct?
a) Start tags: <section>
b) End tags: </section>
c) <img src= “abc.jpeg” >ABC</img>
d) None of the mentioned

Explanation: All the mentioned options are valid HTML5 arguments and executes properly.
14. CFGs can be parsed in polynomial time using__________
a) LR parser
b) CYK algorithm
c) SLR parser
d) None of the mentioned

Answer: CYK algorithm parses the CFG in polynomial time while LR parsers do the same in linear time. DCFGs are accepted by DPDAs and parsed using LR parsers or CYK algorithm.
15. Which of the following is a parser for an ambiguous grammar?
a) GLR parser
b) Chart parser
c) All of the mentioned
d) None of the mentioned