Examples based on Context Free Grammar

Let Us Understand Context-free grammar by a few examples :

Example 1: Construct the Context Free Grammar for the language having any number of a's over the set ∑= {a}. Solution: As we know the regular expression for the above language is r.e. = a*      Production rule for the Regular expression is as follows: S → aS    rule 1   S → ε     rule 2   Now if we want to derive a string "aaaaaa", we can start with start symbols.  S   aS    aaS          rule 1   aaaS         rule 1   aaaaS        rule 1   aaaaaS       rule 1   aaaaaaS      rule 1   aaaaaaε      rule 2   aaaaaa   The r.e. = a* can generate a set of string {ε, a, aa, aaa,.....}. We can have a null string because S is a start symbol and rule 2 gives S → ε.

Example 2: Construct a CFG for the regular expression (0+1)* Solution: The CFG can be given by, Production rule (P):   S → 0S | 1S   S → ε   The rules are in the combination of 0's and 1's with the start symbol. Since (0+1)* indicates {ε, 0, 1, 01, 10, 00, 11, ....}. In this set, ε is a string, so in the rule, we can set the rule S → ε.

Example 3: Construct a CFG for a language L = {wcwR | where w € (a, b)*}. Solution: The string that can be generated for a given language is {aacaa, bcb, abcba, bacab, abbcbba, ....} The grammar could be: S → aSa   rule 1   S → bSb   rule 2   S → c        rule 3   Now if we want to derive a string "abbcbba", we can start with start symbols. 1.    S → aSa    2.    S → abSba       from rule 2   3.    S → abbSbba     from rule 2   4.    S → abbcbba     from rule 3   Thus any of this kind of string can be derived from the given production rules.

Example 4: Construct a CFG for the language L = anb2n where n>=1. Solution: The string that can be generated for a given language is {abb, aabbbb, aaabbbbbb....}. The grammar could be: S → aSbb | abb   Now if we want to derive a string "aabbbb", we can start with start symbols. S → aSbb   S → aabbbb

 

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.