What do you understand by Derivation?

Derivation is the process of passing or verifying a string by generating a language from the given grammar which is also known as production rules, the non-terminals(variables) are replaced by the corresponding strings of the right-hand side (RHS) of the production.

But if there is more than one non-terminal(variable) were present in any grammar, then which of the ones will be replaced must be determined. Depending on this selection, the derivation is divided into two parts:     

Leftmost derivation

Leftmost derivation: In this type of derivation, we replace only the leftmost non-terminal(variable) by some production rule at each step of the generating process of the language from the grammar.

·         The process of deriving a string by expanding the leftmost non-terminal at each step is called as leftmost derivation.

·         The geometrical representation of leftmost derivation is called as a leftmost derivation tree.

Rightmost derivation

Rightmost derivation: In this type of derivation, we replace only the rightmost non-terminal(variable) by some production rule at each step of the generating process of the language from the grammar.

·         The process of deriving a string by expanding the rightmost non-terminal at each step is called as rightmost derivation.

·         The geometrical representation of the rightmost derivation is called a rightmost derivation tree.

Example

Construct the string abbbb from the grammar given below by using LMD and RMD.

Solution :

(Note: Keep your mobile horizontally for better reading)

 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.