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

1. Which of them have XML as their default format?
a) IWork
b) LibreOffice
c) OpenOffice
d) All of the mentioned

Answer: d
Explanation: More that hundred of document formats using XML syntax have been developed, including RSS, Atom, SOAP and XHTML.

2. Which of the following is an example of inherent ambiguous language?
a) {an|n>1}
b) {anbncmdm| n,m > 0}
c) {0n1n|n>0}
d) None of the mentioned

Answer: b
Explanation: This set is context-free, since the union of two context-free languages is always context free.

3. A non deterministic two way, nested stack automaton has n-tuple definition. State the value of n.
a) 5
b) 8
c) 4
d) 10

Answer: d
Explanation: The 10-tuple can be stated as: NSA= ‹Q,S,G,d,q0,Z0,F,[,],]›.

4. Which of the following automata takes queue as an auxiliary storage?
a) Finite automata
b) Push down automata
c) Turing machine
d) All of the mentioned

Answer: c
Explanation: Pushdown Automaton uses stack as an auxiliary storage for its operations. Turing machines use Queue for the same.

5. Which among the following is true for the given statement?
Statement :If there are strings R and T in a language L so that R is prefix of T and R is not equivalent to T.
a) No DPDA can accept L by empty stack
b) DPDA can accept L by an empty stack
c) L is regular
d) None of the mentioned

Answer: a
Explanation: If M is a DPDA accepting L by an empty stsck, R and T are distinct strings in L, and R is a prefix of T, then the sequence of moves M must make in order to accept R leaves the stack empty, since R?L. But then T cannot be accepted, since M cant move with an empty stack.

6. Which of the following statement is false?
a) For non deterministic PDA, equivalence is undecidable
b) For deterministic PDA, equivalence is decidable
c) For deterministic PDA, equivalence is undecidable.
d) None of the mentioned

Answer: c
Explanation: Geraud proved the equivalence problem decidable for Deterministic PDA .

7. State true or false:
Statement: For every CFL, G, there exists a PDA M such that L(G) = L(M) and vice versa.
a) true
b) false

Answer: a
Explanation: There exists two lemma’s such that:
a) Given a grammar G, construct the PDA and show the equivalence
b) Given a PDA, construct a grammar and show the equivalence

8. Which of the following strings do not belong the given regular expression?
(a)*(a+cba)
a) aa
b) aaa
c) acba
d) acbacba

Answer: d
Explanation: The string acbacba is unacceptable by the regular expression (a)*(a+cba).

9. a?b
Restriction: Length of b must be atleast as much length of a.
Which of the following is correct for the given assertion?
a) Greibach Normal form
b) Context Sensitive Language
c) Chomsky Normal form
d) Recursively Ennumerable language

Answer: b
Explanation: A context-sensitive grammar (CSG) is a formal grammar in which the left-hand sides and right-hand sides of any production rules may be surrounded by a context of terminal and non terminal symbols. Context-sensitive grammars are more general than context-free grammars, in the sense that there are some languages that cannot be described by context-free grammars, but can be described by CSG.

10. For the given set of code, the grammar representing real numbers in Pascal has error in one of the six lines. Fetch the error.
(1) ->
(2) -> | epsilon
(3) -> | epsilon
(4) -> ‘E’ | epsilon
(5) -> + | – | epsilon
(6) -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
a) 3
b) 4
c) 2
d) No errors

Answer: a
Explanation:
–>
–> | epsilon
–> ‘.’ | epsilon
–> ‘E’ | epsilon
–> + | – | epsilon
–> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

11. Given:
S->…->xAy->…->w
if ____________, then A is useful, else useless symbol.
a) A is a non terminal
b) A is a terminal
c) w Î L
d) w Ë L

Answer: c
Explanation: Whatever operation we perform in intermediate stages, if the string produced belongs to the language, A is termed as useful and if not, not a useful variable.

12. Consider G=({S,A,B,E}, {a,b,c},P,S), where P consists of S ?AB, A ?a, B ?b and E ?c.
Number of productions in P’ after removal of useless symbols:
a) 4
b) 3
c) 2
d) 5

Answer: a
Explanation:
P’= S->AB, A->a, B-> b,
V’={S, A, B},
?’={a, b}

13. Given Grammar:
T-> T+R| R
R-> R*V| V
V->(T)| u
When unit productions are deleted we are left with
T-> T+R| _______|(T)| u
R->R*V|(T)| u
V-> (T)| u
Fill in the blank:
a) T*V
b) T+V
c) R*T
d) R*V

Answer: d
Explanation: The grammar produced after the elimination of unit production is:
T-> T+R| R*V| (T)| u
R->R*V|(T)| u
V-> (T)| u

14. With reference to the process of conversion of a context free grammar to CNF, the number of variables to be introduced for the terminals are:
S->ABa
A->aab
B->Ac
a) 3
b) 4
c) 2
d) 5

Answer: a
Explanation: According to the number of terminals present in the grammar, we need the corresponding that number of terminal variables while conversion.

15. Using pumping lemma, which of the following cannot be proved as ‘not a CFL’?
a) {aibici|i>=0}
b) {ss|s?{a,b}*}
c) The set legal C programs
d) None of the mentioned

Answer: d
Explanation: There are few rules in C that are context dependent. For example, declaration of a variable before it can be used.