2
$\begingroup$

Let be:

  • Uppercase letters — non-terminal symbols.
  • Lowercase letters — terminal symbols.

Possible cases:

  1. The number of words is 0 (infinite substitutions). Examples: $$\{S \rightarrow aS\}, \\ \{S \rightarrow aF, F \rightarrow aS \}, \\ \{S \rightarrow aA, S \rightarrow A, A \rightarrow FS, F \rightarrow t\}$$
  2. The number of words is finite and $\ge 1$. Examples: $$\{S \rightarrow a\}, \\ \{S \rightarrow aF, F \rightarrow a \}, \\ \{S \rightarrow aA, S \rightarrow A, A \rightarrow FP, F \rightarrow k, P \rightarrow t \}$$
  3. The number of words is infinite. Examples: $$\{S \rightarrow a, S \rightarrow aS \}, \\ \{S \rightarrow aF, F \rightarrow a, F \rightarrow aS \}, \\ \{S \rightarrow Sb, S \rightarrow aA, A \rightarrow Sb, A \rightarrow Ab, A \rightarrow b \}$$

Is it possible to create a universal algorithm that determines which of these cases a given grammar belongs to?

Any grammar can be represented as a directed graph (right?). However, a graph can have several connectivity components. And this leads me to a dead end.
Example: $$\{ S \rightarrow a, S \rightarrow aS, bbbbS \rightarrow b \} \\ \space \mathrm{infinite} \space \mathrm{for} \space S, \\ \mathrm{but} \space \mathrm{finite} \space \mathrm{for} \space bbbbS.$$

Hence, it is clear that the algorithm must take the start word and rules as input.

$\endgroup$
3
  • $\begingroup$ in your last example, it is empty for $S$ and not infinite. You will never generate any terminal word when starting at $S$. $\endgroup$
    – nir shahar
    Sep 28 at 20:04
  • $\begingroup$ Also, is your grammer context free? In this case the rule $bbbbS\rightarrow S$ isn't allowed. Otherwise, Yuval's answer might not help in this case - since it relies on the context-freenes of the grammar. $\endgroup$
    – nir shahar
    Sep 28 at 20:08
  • $\begingroup$ @nir-shahar I forgot to add S->a, updated the question. I originally thought about Type-0 grammars. But then I saw the Halting problem and decided that there was no universal algorithm (for Type-0 grammars). $\endgroup$ Sep 29 at 4:15
2
$\begingroup$

In order to decide whether a context-free grammar generates the empty language or not, you can compute the set of productive nonterminals. A nonterminal $A$ is productive if there is a rule $A \to \alpha$ where all nonterminals in $\alpha$ are already known to be productive. The set of productive nonterminals can be computed iteratively using the definition. The grammar generates the empty language iff the start symbol is not productive.

In order to determine whether the language generated by a context-free grammar is infinite or not, you can use the pumping lemma. First you need to convert the grammar into Chomsky normal form. Then, there are thresholds $n_1,n_2$, depending on the number of nonterminals, such that the language generated by the grammar is infinite iff it contains a word whose length is between $n_1$ and $n_2$ (in the case of regular grammars, you can take $n_1 = n$ and $n_2 = 2n-1$, where $n$ is the number of nonterminals, but for general context-free grammars, $n_1,n_2$ are exponential in $n$); this is a consequence of the pumping lemma. This is not a very efficient algorithm, unfortunately, but it shows that the problem is decidable.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.