1. Which of the following conversion is not feasible?
a) Regular expression to automaton conversion
b) Automaton to Regular Expression Conversion
c) NFA to DFA
d) None of the mentioned
View Answer
Explanation: Each of the four formats of representation of the regular language be it, DFA, NFA, Regular Expression or e-NFA can be converted to the rest three forms.
2. Which of the following are decision properties?
a) Emptiness
b) Infiniteness
c) Membership
d) All of the mentioned
View Answer
Explanation: Emptiness, Infiniteness and Membership are the decision properties of any language class. Example: Is the language L empty? Or Is w, a string belongs to the regular language L?
a) L1*
b) L2UL1
c) L1.L2
d) All of the mentioned
View Answer
Explanation: The following is a theorem which states the closure property of context free languages which includes Kleene operation, Union operation and Dot operation.
(011+1)*(01)*
a) 4
b) 3
c) 5
d) 6
View Answer
Explanation: The grammar can be written as:
S->BC
B->AB|e
A->011|1
C->DC|e
D->01
Statement: Recursive inference and derivation are equivalent.
a) Yes
b) No
View Answer
Explanation: Yes, they are equivalent. Both the terminologies represent the two approaches of recursive inferencing.
a) h
b) h+1
c) h-1
d) 2h
View Answer
Explanation: It is the basic implication of Parse tree theorem (assuming CNF). If the height of the parse tree is h, then |w| <=2h-1.
a) Left aligned left right parser
b) Look ahead left to right parser
c) Language Argument left to right parser
d) None of the mentioned
View Answer
Explanation: LALR stands for Look ahead left to right parsers. It has more language recognition power than LR(0) parser.
8. State true or false:
Statement: BNF is a metasyntax used to express CFG
a) True
b) False
View Answer
Explanation: BNF is a metasyntax used to express context free grammar, moreover a formal way to express the language.
a) Context Regular Grammar
b) Regular Grammar
c) Context Sensitive Grammar
d) None of the mentioned
View Answer
Explanation: Regular grammar is a subset of Context free grammar. The CFGs which produces a language for which a finite automaton can be created is called Regular grammar.
10. The following move of a PDA is on the basis of:
a) Present state
b) Input Symbol
c) Both (a) and (b)
d) None of the mentioned
View Answer
Explanation: The next operation is performed by PDA considering three factors: present state,symbol on the top of the stack and the input symbol.
11. The instantaneous PDA is has the following elements
a) State
b) Unconsumed input
c) Stack content
d) All of the mentioned
View Answer
Explanation: The instantaneous description of a PDA is represented by 3 tuple:
(q,w,s)
where q is the state, w is the unconsumed input and s is the stack content.
12. The transition a Push down automaton makes is additionally dependent upon the:
a) stack
b) input tape
c) terminals
d) none of the mentioned
View Answer
Explanation: A PDA is a finite machine which has an additional stack storage. Its transitions are based not only on input and the correct state but also on the stack.
13. Which of the following relates to Chomsky hierarchy?
a) Regular<CFL<CSL<Unrestricted
b) CFL<CSL<Unrestricted<Regular
c) CSL<Unrestricted<CF<Regular
d) None of the mentioned
View Answer
Explanation: The chomsky hierarchy lays down the following order: Regular<CFL<CSL<Unrestricted
a) Greibach
b) Backus
c) Chomsky
d) None of the mentioned
View Answer
Explanation: Chomsky hierarchy decide four type of language :Type 3- Regular Language, Type 2-Context free language, Type 1-Context Sensitive Language, Type 0- Unrestricted or Recursively Ennumerable language.
X->aX
Which among the following is correct with respect to the given assertion?
a) Left Recursive Grammar
b) Right Recursive Grammar
c) Non Recursive Grammar
d) None of the mentioned
View Answer
Explanation: The grammar with right recursive production is known as Right recursive grammar. Right recursive production is of the form X->aX where a is a terminal and X is a non terminal.
