Example to generate Parse tree from the given grammar

Let us understand an example to find the parse tree for generating the string 0100110 from the following grammar.

          S → 0S/1AA
          A → 0/1A/0B
          B → 1/0BB

Explaination :

To generate the string 0100110 from given context free grammar, the Left most derivation will be :

S → 0S → 01AA → 010BA → 0100BBA → 01001BA → 010011A → 0100110

To generate the string 0100110 from given context free grammar, the Right most derivation will be :

S → 0S →01AA → 01A0 → 010B0 → 0100BB0 → 0100B10 → 0100110

Although, when you find that both LMD and RMD have the same parse tree, the way to draw the parse tree is different.

Note: When you are told to generate a parse tree, you can generate that by the leftmost derivation or the rightmost derivation.

 Also, Study about: 

• Mealy Machine
• Moore Machine
• Rice Theorem
• Brief about Turing Machine
• Multi Dimension Turing Machine
• Multiple Turing Machine
• Parikh Theorem in TOC
• Parse Tree or Derivation Tree
• What do you Understand by Derivation
• MyHill Nerode Theorem
• Minimize Myhill Nerode Theorem
• Push Down Automata
• Know Where we use Automata
• What do you understand by Derivation of Grammar
• What is Context-free Grammar
• Example based on CFG
• Regular Expression in TOC
• What is Two-way infinite Turing machine?
• Example to generate Parse tree from the given grammar

Also Read, some interview tips

• Why Should I Hire You?
• What are your weaknesses?
• What are your greatest strengths?
• Tell me about yourself.
• What's the reason behind leaving your current position at your company?
• Do You Know how the power of Keywords impacts on Resume?
• Top 8 Proofreading Tips and Techniques in 2022.
• Top Ten Technical Resume Writing Tips in 2022.
• Tips for your resume before you get entry to Job Market
• What Questions you can ask HR during the Interview.
• How to make an impressive resume?
• Best Resume writing Technique.
• What Questions you can ask HR during the Interview.