Final Term Paper Current CS402 Theory of Automata 9 August 2010

Fill it with suitable word

• A Push down Automate consists of and input TAPE with ----------many location in one direction. (Marks 2)
• Construct RE for the language having words of even length over ∑= {a.b} (2 Mark)
• If two FAs have no final states then what will be the final state of their union? (2 mark)
• Write true or false for the following statement
  (a) Dead state is must in NFA
  (b) There is a union path for each valid string (called a word) in NFA. (2 mark)
• Write the three different parsing techniques? (3 mark)
• Explain first two rules of defining all possible production of CFG of the “Row language” (5 mark)
• Construct corresponding CFG for the given language
  (1) All words of even length but not multiple of 3.
  (2) Palindrome (both even and odd palindrome). (5 mark)
• Question #8 ) Is the following CFG ambiguous? How can you remove the ambiguity?
  S→aS│bS│aaS│