Formal Languages and Automata Theory Mid - I, February - 2012

1.____________ is a set of strings.
  • Languages
  • Grammar
  • NFA
  • DFA
Answer: A
2.Let 'a' is any symbol, 'x' is a palindrome then which of the following is not a palindrome.
  • x
  • a
  • axa
  • ax
Answer: D
3.Application of Finite Automata is __________
  • Parser
  • scanner
  • lexical analyzer
  • semantic analyzer
Answer: C
4.FSM can recognize __________
  • any grammar
  • only regular grammar
  • only CFG
  • any unambiguous grammar
Answer: B
5.Let maximum number of states in DFA=64. Then it's equivalent NFA has
  • 2
  • 4
  • 6
  • 8
Answer: D
6.A melay machine is a _______ tuple.
  • 4
  • 5
  • 6
  • 7
Answer: C
7.Let r and s are regular expressions denoting the languages R and S. Then (r*) denotes ________
  • RS
  • R*
  • RUS
  • R+
Answer: B
8.(e 00)* = _________
  • e
  • 0
  • e0
  • (00)*
Answer: D
9.Regular grammars are also called as ___________
  • Type 0
  • Type 1
  • Type 2
  • Type 3
Answer: D
10.Which of the following is related to regular grammar?
  • Right linear
  • left linear
  • right linear & left linear
  • CFG
Answer: C
11.____________ is a finite sequence of symbols.
Answer: strings
12.In finite automata, symbol Q represents ___________
Answer: finite set of states
13.A grammar is a ___________ device.
Answer: generative
14.Let M= {Q, S, q0, F}, F= {q0}, S= {0, 1}. Then (q0,110) __________
Answer: q^2
15.A Moore machine is a ___________ tuple.
Answer: 6
16.0(00)*(e 0)1 1= _________.
Answer: 00*1+1
17.___________ grammar is also known as Type 3 grammar.
Answer: regular
18.The logic of pumping lemma is a good example of ___________.
Answer: pigeon hole principle
19.In finite automata, the symbol S represents _____________.
Answer: start of symbol
20.In transition diagrams, a state encircled by another represents __________ state.
Answer: final (or) end