A context-free grammar (CFG) is a set of recursive rewriting rules (or productions) used to generate patterns of strings. A CFG consists of the following components:
a set of terminal symbols, which are the characters of the alphabet that appear in the strings generated by the grammar.
a set of non-terminal symbols, which are placeholders for patterns of terminal symbols that can be generated by the non-terminal symbols.
a set of productions, which are rules for replacing (or rewriting) non-terminal symbols (on the left side of the production) in a string with other non-terminal or terminal symbols (on the right side of the production).
a seed, which is a special non-terminal symbol that appears in the initial string generated by the grammar.
To generate a string of terminal symbols from a CFG, we:
Begin with a string consisting of the start symbol;
Apply one of the productions with the start symbol on the left hand side, replacing the start symbol with the right hand side of the production;
Repeat the process of selecting non-terminal symbols in the string, and replacing them with the right hand side of some corresponding production, until all non-terminals have been replaced by terminal symbols.
For example, this specification: A = BD B = bB | b | Bb D = dD D = d with A as the seed represents the set of words that have one or more b's followed by one or more d's (bd, bbd, bddd, bbbddd, etc.). Above production grammar contains string “bbd”. So your task is to find out the given string can be formed by given grammar or not. If that string can formed by the given grammar then return true otherwise false.
Submit an article or tip