Working with the Prioritized-Choice Rule

The following exercises demonstrate several cases of valid but problematic CGFs with discussion and prioritized-choice solutions. They are arranged from trivial to head-scratching and it is suggested that you try them in the order presented.

exercise 1 – longest alternative first
exercise 2 – repetitions
exercise 3 – non-trivial
exercise 4 – impossible (almost)

repetitions

Be suspicious any time a repetition is followed by another term, e.g. *A B. If the languages L{A} and L{B} overlap, you've got a problem. The simple grammar below is obviously meant to be interpreted as, "one or more letters a". And it is a valid CFG statement of that specification. But try it and you will see that, using the prioritized-choice rule, it fails for any string of letters a. The reason is that the first term always matches the entire string and the last term then fails. (If you like, examine the trace - Tutorial 4 - to see this explicitly.)

In this case the fix (e.g. fix 1 or fix 2) is trivial. But if the definitions of A and B have any complexity to them at all, it probably won't be.