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

Wednesday 14 October 2020

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

Write the name of different types of grammer? Explain Chomsky classification of grammer? Convert into GNF? Write closure property of context... thumbnail 1 summary
  • Write the name of different types of grammer?
  • Explain Chomsky classification of grammer?
  • Convert into GNF?
  • Write closure property of context free language and also write decision algorithm for CFL?
  • Define derivation and language.

  • Construct a reduced grammar equivalent to the grammar
  • Construct a grammar like greibach normal form

  • Consider the grammar: 
S=S+S/S*S/id
Construct leftmost derivation, rightmost derivation and derivation tree for the string 
W=id+id*id

  • Define grammar?
  • Define context free grammars?
  • Write a CFG which generates the string of balanced parenthesis. Also show that the following group of parenthesis is accepted by the CFG
(()((())))
  • What do you mean by ambiguity in context free grammars. If G is the grammar S->SbS|a, then show that G is ambiguous
  • Write the name of different grammars.
  • Expain pumping lemma for context free language with examples.
  • Consider the grammar S->S+S|S*S|a|b
  • Construct leftmost derivation, right most derivation and derivation tree for the string ab+c. also show that the grammar is ambiguous.
  • Explain relation among types of grammars.
  • Context free language L:{WCWR|W C (0+1)*} can be accepted by which automaton.
1.PDA, 2.NPDAM, 3.TM, 4.ALL
  • Explain deterministic and nondeterministic push down automata with example.
  • design a turing machine m to recognize the language:
{1n2n3n | n>=1}
  • Define PCP and MPCP. Does the PCP with two lists:
X=(b, bab3, ba) and
Y=(b3,ba,a) have a solution.