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

1. Complement of regular sets are _________
a) Regular
b) CFG
c) CSG
d) RE

2. Which of the following is true?
a) (01)*0 = 0(10)*
b) (0+1)*0(0+1)*1(0+1) = (0+1)*01(0+1)*
c) (0+1)*01(0+1)*+1*0* = (0+1)*
d) All of the mentioned
3. For a _________ state DFA, the time taken for DFA-NFA conversion is O(n).
a) n
b) n1/2
c) n2
d) 2n
4. For the given syntax of sed, which among the following is not a correct option?
General syntax of sed: /pattern/action
a) / are used as delimiters
b) pattern refers to a regular expression
c) pattern refers to the string to be matched
d) action refers to the command
5. a? is equivalent to
a) a
b) a+F
c) a+?
d) wrong expression
6. Which of the following obey the closure properties of Regular language?
a) Homomorphism
b) Inverse Homomorphism
c) Reversal
d) All of the mentioned
7. Which of the following cannot be used to decide whether and how a given regexp matches a string:
a) NFA to DFA
b) Lazy DFA algorithm
c) Backtracking
d) None of the mentioned
8. NFA to DFA conversion is done via
a) Subset Construction method
b) Warshalls Algorithm
c) Ardens theorem
d) None of the mentioned
9. Which of the following statement is correct?
a) All Regular grammar are context free but not vice versa
b) All context free grammar are regular grammar but not vice versa
c) Regular grammar and context free grammar are the same entity
d) None of the mentioned
10. Which of the following the given language belongs to?
L={ambmcm| m>=1}
a) Context free language
b) Regular language
c) Both (a) and (b)
d) None of the mentioned
11. State true or false:
Statement: Every right-linear grammar generates a regular language.
a) True
b) False
12. Which of the following statement is false in context of tree terminology?
a) Root with no children is called a leaf
b) A node can have three children
c) Root has no parent
d) Trees are collection of nodes, with a parent child relationship
13. Which of the following is false for a grammar G in Chomsky Normal Form:
a) G has no useless symbols
b) G has no unit productions
c) G has no epsilon productions
d) None of the mentioned
14. Which of the following parser performs top down parsing?
a) LALR parser
b) LL parser
c) Recursive Accent parser
d) None of the mentioned
15. The _______ table is created by YACC.
a) LALR parsing
b) LL parsing
c) GLR parsing
d) None of the mentioned