Learn · Theory of Automata, Formal Languages and Computation

Lecture 7 of 42Grammars: Properties of Context Free Grammars

GREIBACH NORMAL FORM FOR CFG

Prof. Kamala Krithivasan · IIT Madras

Credits and licence

From
Theory of Automata, Formal Languages and Computation, IIT Madras (at NPTEL)
Licence
CC BY-NC-SA, as NPTEL states it. Non-commercial use only.
Attribution
NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
Who can watch
Tweens profiles and older. How courses are placed

All the lectures

  1. GRAMMARS AND NATURAL LANGUAGE PROCESSING Video
  2. GRAMMARS AND LANGUAGES GENERATED Video
  3. GRAMMARS AND LANGUAGES GENERATED (Contd) Video
  4. AMBIGUITY IN CFG Video
  5. SIMPLICATION OF CFG Video
  6. REMOVAL OF UNIT PRODUCTIONS , CHOMSKY NORMAL FORM FOR CFG Video
  7. GREIBACH NORMAL FORM FOR CFG Video
  8. FINAL STATE AUTOMATA Video
  9. NON DETERMINISTIC FSA Video
  10. NON DETERMINISTIC FSA (Contd) Video
  11. NON DETERMINISTIC FSA WITH E(Epsilon)- MOVES Video
  12. EQUIVALENCE BETWEEN FSA AND TYPE 3 GRAMMARS Video
  13. REGULAR EXPRESSIONS , REGULAR EXPRESSIONS TO NFSA Video
  14. DFSA TO REGULAR EXPRESSIONS Video
  15. PROBLEMS AND SOLUTIONS-I Video
  16. PUMPING LEMMAS FOR REGULAR SETS AND CFL Video
  17. MYHILL - NERODE THEOREM Video
  18. MINIMIZATION OF DFSA Video
  19. FSA WITH OUTPUT MOORE AND MEALY MACHINES Video
  20. PUSHDOWN AUTOMATA Video
  21. PUSHDOWN AUTOMATA , EQUIVALENCE BETWEEN ACCEPTANCE BY EMPTY STORE AND ACCEPTANCE BY FINAL STATE Video
  22. PUSHDOWN AUTOMATA CFG TO PDA Video
  23. PUSHDOWN AUTOMATA PDA TO CFG Video
  24. PROBLEMS AND SOLUTIONS-II Video
  25. PROBLEMS AND SOLUTIONS - III Video
  26. TURING MACHINES Video
  27. TURING MACHINES (Contd) Video
  28. TURING MACHINE AS ACCEPTOR , TECHNIQUES FOR TM CONSTRUCTION Video
  29. GENERALIZED VERSIONS OF TURING MACHINES Video
  30. TURING MACHINE AS A GENERATING DEVICE Video
  31. RECURSIVE SETS , RECURSIVELY INNUMERABLE SETS , ENCODING OF TM , HALTING PROBLEM Video
  32. PROBLEMS AND INSTANCES , UNIVERSAL TM , DECIDABILITY Video
  33. RICE'S THEOREM , LINEAR BOUNDED AUTOMATA , PROPERTIES OF TM Video
  34. POST'S CORRESPONDENCE PROBLEMS Video
  35. POST'S CORRESPONDENCE PROBLEMS (Contd), TIME AND TAPE COMPLEXITY OT TM Video
  36. NP - COMPLETE PROBLEMS , COOK'S THEOREM Video
  37. NP - COMPLETE PROBLEMS (Contd) Video
  38. REGULATED REWRITING Video
  39. L - SYSTEMS Video
  40. GRAMMAR SYSTEMS Video
  41. DNA COMPUTING Video
  42. MEMBRANE COMPUTING Video