In formal language theory, a context-free grammar (CFG) is a certain type of formal grammar: a set of production rules that describe all possible strings in a given formal language. Production rules are simple replacements.
replaces
with . There can be multiple replacement rules for any given value. For example,
means that
can be replaced with either or .
In context-free grammars, all rules are one-to-one, one-to-many, or one-to-none. These rules can be applied regardless of context. The left-hand side of the production rule is always a non-terminal symbol. This means that the symbol does not appear in the resulting formal language. So in our case, our language contains the letters
and
but not Rules can also be applied in reverse to check whether a string is grammatically correct according to the grammar.
Here is an example context-free grammar that describes all two-letter strings containing the letters
or .
If we start with the non-terminal symbol
then we can use the rule to turn into . We can then apply one of the two later rules. For example, if we apply
to the first we get . If we then apply
to the second we get . Since both and are terminal symbols, and in context-free grammars terminal symbols never appear on the left hand side of a production rule, there are no more rules that can be applied. This same process can be used, applying the last two rules in different orders in order to get all possible strings within our simple context-free grammar.
Project 6, Part 1a (student_cfg.txt)- Part 1b