Context-Free Grammars: How to understand substitution rules

Question

I am at a bit of a loss when it comes to understanding how to apply substitution rules for checking if a string is accepted / rejected for a given context-free grammar (CFG).

Suppose I have been given the CFG G, as specified below:

I know the grammar consists of the following:

• Variables: {R, X, S, T}
• Terminals: {a, b}
• R is the start variable

Question

How can I check if the string ab is accepted (i.e. that ab is in L(G))? That is, how does one apply the substitutions rules to reach a conclusion? Is there a good way to backtrack the derivation procedure?

Any help on how to understand this is highly appreciated!

Answer 1

For your given example it is simple to see it, in general (and if you want to implement this on a computer) the standard algorithm to decide the word problem for context free languages is the CYK algorithm (after Cocke-Younger-Kasami).

Answer 2

In genereal, a string is in the language of a grammar if and only if there exists a derivation from the start symbol to the string of terminal nodes by recursively applying substitution rules.
The way you apply those subsitution rules totally depends on which parsing algorithm you chooose, and depending on the type of grammar (e.g. whether you have recursion in it or not), the different algorithms might differ in their power to succeed, but apart from that, they are all more or less equivalent in that they try to proof a string's grammaticality by computing derivations from the start symbol to the terminal nodes.

You need to apply the subsitution rules recursively until you get a derivation from the start symbol to the terminal nodes.

In this example, R is the start symbol, so you apply the substitution rule and get two possibilities: either XRS or S. You can now decide which path to take; let's say XRS.

So you check the first non-terminal node in XRS, which is X. X goes to a or b - which is fine, you pick as and X is done.
Next, you need to go to R, i.e. you apply the rule again. This is where you should notice that this path doesn't lead to success: Whichever X you choose, you will need to check three non-terminal nodes non of which goes to an empty string, so for a string of length 2 (ab), a subsitution rule with three non-terminals won't lead to success.

So you need to backtrack to the point at which you could have made another decision, which is R -> XRX | S. You chose to take XRX which failed, so let's try out S instead. S goes to aTb or bTa.
Here you already have your first terminal node: a is the first element of your string and you just substituted S for a, so this is fine.
Next you need to check for T. Since the element that follows in the rule is b and you need b for your string, you need to insert an empty string between a and b, so T should lead to an epsilon.
Which works: Looking at the substitution rule for T, you see that on the right-hand side at the rule, there is the empty string.

And now you're done: You have found a way to derive the string "ab" by the grammar rules, starting from R and recursively applying substitution rules.
Therefore, the string "ab" is in the langugage of G.

The procedure I just described was basically a top-down parsing alrorithm: You start with the non-terminal nodes and recursively expand the substitution rules until you reach the terminal nodes. In computer science, this is sometimes called "expand and consume", because you expand the left-hand-side of the rule to the more specific right-hand-side of the rule and consume those terminal nodes that appear on the right-hand-side of the rule you have just expanded.
The opposite procedure would be bottom-up: Starting with the terminal nodes, you check which non-terminals you can build up with it (i.e., to which left-hand side of the rule the string might correspond to) and whether there is a way to reach the starting symbol at the end. This is also commonly called shift-reduce parsing, since you shift your input symbol onto a stack and try to reduce what's on there to the higher terminal nodes left-hand-sides of the rules.
There is quite a variety of other parsing algorithms; e.g. the Early algorithm, which is basically a combination of top-down and bottom-up, or CYK, as mentioned in a previous answer.

It is important to note that here is not THE way of deriving a string from a grammar, but actually quite a lot; the way I described is just the most intuitive one for me.

I general, I strongly recommend you to consult literature on parsing, which is mostly used in computer science, but also in linguistics and surely well-readable for mathematicians. Of course you don't need to go into depth of how to implement a parsing algorithm or how to use CFGs in linguistics, but the type of the question you asked suggests that you don't have an overview yet on how to work with such grammars in general.