SUBJECT MATERIAL, EBOOKS, IMPORTANT QUESTION , ASSIGNMENT QUESTION, OLD QUESTION PAPER

Wednesday 12 August 2020

Theory of Computation (TOC) Important / Assignment Question Download UNIT 1

2 Marks Construct the DFA which will accept the string ending with qb or ba? Define Mealy and Moore machine? What will be the length of ... thumbnail 1 summary

2 Marks

  • Construct the DFA which will accept the string ending with qb or ba?
  • Define Mealy and Moore machine?
  • What will be the length of output string for a Moore machine and a Mealy machine if the input string is the length n, Choose the correct one
    • n, n+1
    • n,n
    • n+1, n
    • n+1, n+1 
  • Define Transaction Graph.
  • Write the Tuple Representation of FA.
  • Transition function of NFA is defined as :

 7 Marks

  • Minimize the following DFA by using my hill nerode theorem.

  • Consider the mealy machine describe by the following transition table, construct the moore machine which is equivalent of mealy m/c?
 
  • Write difference between NFA and DFA?
  • Construct a DFA equivalent to the NDFA M where transition diagram is given by figure.
  •  construct a Moore machine equivalent to the Mealy machine M defined by the table:
  • Define Myhill Nerode theorem. Explain the properties of FSM.
  • Design a DFA which accepts substring "USE" over ∑=HOUSE".
  • Design a DFA to accept string of a and b ending with ab or ba.
  • Minimize the following DFA:
  • Consider the following NFA with ε transitions transform this NFA with ε transitions to an NFA without ε transitions.
  • Minimize the following DFA, represented using transition diagram.
  • Write short notes on
    • Two way finite automata
    • Mealy machines
  •  Construct a DFA equivalent to the following NFA:
 
  •  Construct a Moore machine equivalent to the Mealy Machine:
 
  •  Construct a FA for the set of strings w over{a,b}* such that w ends with sub-string ab.
  • Construct a Moore machine equivalent following mealy machine. Also construct transition diagram for same.
  • Write short notes on following
    • My-hill Nerode theorem
    • Two way finite automata.
  • Construct a minimum state automata equivalent to following DFA