Decidability
This chapter corresponds to chapter 18 of the second edition of Cohen (1997).
In COS2601 we learned what the term ‘decidable’ means: a problem is
decidable if and only if there exists an effective solution to it that has a ‘yes’
or a ‘no’ answer. Thus a question is decidable if there is an algorithm that
is able to answer the question for every permissible input. The first question
of the chapter, namely the question whether we can tell if two given CFGs
define the same language, is undecidable. It means that there does not exist
an algorithm such that, given any two CFGs, it will always tell us whether
the same language is generated by them. An example of a decidable question
is whether we can tell if a CFG generates any words. It means that there
does exist an algorithm such that we can give it any CFG and it will tell us
whether it generates any word at all.
The proof that a question is decidable is usually not very difficult to un-
derstand. In most cases it consists of an algorithm that answers the relevant
question for any instance, and an explanation of why that algorithm is cor-
rect. Most of the chapter is devoted to such proofs. Proving that a question
is undecidable is usually more difficult. Note that Cohen does not give proofs
that the seven questions at the beginning of the chapter are undecidable.
The algorithms that you meet here are effective but, with exception of the
CYK algorithm, not very efficient. We are, however, involved in the study of
Computer Theory and are interested in what can be done, not in how fast it
can be done. Thus the emphasis in Cohen is on clarity and not on efficiency.
We are going to reformulate two of the algorithms. You should follow
these steps when required to execute one of these algorithms.
Reformulation of the Algorithm given in the proof of
Theorem 42
The input is a CFG. The question is: Is the language generated by the given
CFG empty?
• Step -1: Is S nullable? (Use the blue-paint algorithm of previous chap-
ters to answer the question.)
– Yes: The language is not empty. Halt.
– No: Perform step 0.
• Step 0: Convert the CFG to CNF. Is there a production of the form
S −→ t where t is a terminal?
1
– Yes: The language is not empty. Halt.
– No: Perform step 1.
• Step 1: For each nonterminal N that has some production of the form
N −→ t where t is a terminal or a string of terminals, choose one such
production and throw out all the others for which N is on the lefthand
side. Replace N on the righthand side of all productions by replacing
all occurrences of N with t, thus eliminating N altogether. Go to step
2.
• Step 2: Has S been eliminated?
– Yes: The language is not empty. Halt.
– No: Perform step 3.
• Step 3: Can another nonterminal be eliminated by performing step 1?
– Yes: Perform step 1.
– No: The language is empty. Halt.
Note that the algorithm always halts.
Theorems 43 and 44
The proof of Theorem 43 includes an algorithm which determines whether or
not a specified nonterminal in a given CFG is used in the generation of words.
The algorithm will always give an answer, irrespective of the nonterminal it
is fed. The proof of Theorem 44 includes an algorithm which determines
whether a given CFG generates a finite or an infinite language.
Reformulation of the CYK Algorithm in the proof of
Theorem 45
The input are a CFG and a word w = x1 x2 ...xn . The question is: Does the
given CFG generate the word w?
We give a reformulation of the algorithm.
• Step 0: Rewrite the CFG in CNF. Put i = 0.
• Step 1: Increase i by 1. Write down all the consecutive substrings of
w of length i. For each of those substrings write down the nonterminal
which can produce it (via more than one production if i > 1).
2
• Step 2: Is i = n?
– Yes: Is S among the nonterminals from which the string can be
produced?
∗ Yes: The word w can be produced by the given CFG. Halt.
∗ No: The word w cannot be produced by the given CFG. Halt.
– No: Go to step 1.
Parsing
Given a word in a programming language, the task of a compiler is to deter-
mine what that word means. If there is an unambiguous CFG that generates
this language, a compiler can use the derivation of the word in this gram-
mar to determine the meaning of the word. Parsing is the finding of such a
derivation. Although an important topic, in this module all that you need to
know about parsing is an idea of how to perform top-down and bottom-up
parsing and what a pushdown transducer is.
