Formal Languages and Automata Theory Mid - II, April - 2012

1.CFG is not closed under
  • Union
  • kleene star
  • complementation
  • product
Answer: C
2.Context free languages are closed under “inverse homomorphism” is ________
  • True
  • false
  • true or false
  • can’t say
Answer: A
3.Deterministic push down automaton:
  • RL
  • CFL
  • Recursively enumerable language
  • DCFL
Answer: D
4.Any TM is more powerful than finite state machine because
  • Tape movement is confined to one direction
  • It has no finite state control
  • It has the capability to remember arbitrary long inputs symbols
  • TM is not powerful than FSM
Answer: C
5.The grammar S -> aAb, A -> aAb|a is
  • LR(1)
  • LR(0)
  • LR(2)
  • LR(3)
Answer: A
6.Turing machine is ___________
  • Recursively enumerable language
  • RL
  • CFL
  • CSL
Answer: A
7.The language [wwr] is accepted by _________
  • DPDA not by a NPDA
  • DPDA and NPDA
  • NPDA not by a DPDA
  • cannot say
Answer: C
8.If S number is the number of states in NDFA for an input string of length n is
  • linear in n
  • polynomial in n
  • exponential in n
  • depending on automata
Answer: A
9.Any Turing machine with m symbols and n states can be simulated by another TM with just 2 s
Symbols and less than
  • 8mn states
  • 4mn + 8 states
  • 8mn + 4 states
  • mn states
Answer: D
10.A regular language is also known as __________ languages.
  • Type 0
  • Type 1
  • Type 2
  • Type 3
Answer: D
11.A production of the form A -> B A, B T is called ___________ production.
Answer: Unit
12.Context sensitive language is also known as ___________ language.
Answer: Type 1
13.A ____________ problem is a problem to which all the NP problems are polynomially reducible.
Answer: NP hard
14.A CFL for which every CFL is ambiguous is said to be a _____________ ambiguous CFL.
Answer: Inherently
15.The class of unrestricted language corresponds to _________________.
Answer: Turing machine
16.In transition diagram for the Turing machines, the final state is represented by ________.
Answer: Double circled
17.In the notation of Turing machine by 7 tuple , the symbol δ is denoted as __________.
Answer: Transition function
18.In the notation of Turing machine by 7 tuple , the finite set of states is denoted by symbol ____.
Answer: Σ
19.A problem whose language is recursive is said to be ______________.
Answer: Undecidable
20.A class of problems called __________ if there is solution of one decision problem from that family then there will be solution for each and every decision problem from that family.
Answer: NP-complete