<p>Can't one implement that algorithm in linear time as follows? (Warning I haven't proof-read this too carefully, so bugs are likely.)</p>

<p>In what follows whenever I say "production" I mean to include only those that include no terminals.
Build a list, for each non-terminal, of the productions it appears in. For every production $i$ let $c_i$ count how many distinct non-terminals in the right hand side are currently marked non-nullable. Let $Q$ denote a queue of non-terminals that have been marked nullable but not yet processed. Initialize all $c_i$ to the number of distinct non-terminals in the right hand side of production $i$. Initialize all non-terminals to not nullable. For every non-terminal $Z$ generated by production $i$ with $c_i=0$ add $Z$ to $Q$ and mark $Z$ as nullable.</p>

<p>While $Q$ is non-empty, remove an arbitrary non-terminal $X$ from $Q$ and process it as follows. For every production $j$ that $X$ is in, decrement $c_j$. If a $c_j$ becomes zero, check to see if the corresponding non-terminal $Y$ has been marked nullable already. If not, mark $Y$ nullable and add $Y$ to $Q$.</p>

CC BY-SA 2.5
2010-10-27T00:05:31.657Z
Unless I'm missing something I think your algorithm should work. I just find it very odd that if I search the internet for an algorithm for this problem, I get over half a dozen hits on the first page describing some variation of the algorithm I described in my first post - why give a n-squared algorithm if a simple linear algorithm exists?
Alex ten Brink
CC BY-SA 2.5
2010-10-27T14:46:25.597Z
One likely reason for giving the quadratic algorithm is that it's even simpler. If you just want to give people an understanding of nullability hiding implementation details makes sense.
Warren Schudy
CC BY-SA 2.5
2010-10-26T23:36:25.597Z
2010-10-26T23:36:25.597Z
Warren Schudy
<p>For a given context free language G, we call a nonterminal $A_i$ <em>nullable</em> if $A_i \rightarrow^* \epsilon$, ie we can derive the empty string from $A_i$ after applying a finite number of productions.</p>

<p>There is a simple algorithm for determining which nonterminals of a grammar are nullable as can be found <a href="http://www.math.grin.edu/~rebelsky/Courses/CS362/2004S/Outlines/outline.16.html">here</a>:</p>

<p>We start by considering all nonterminals as not nullable. We mark all $A_i$ as nullable if there is a production $A_i \rightarrow \epsilon$. We then loop over all other productions $A_i \rightarrow B_1 B_2 \dots B_k$ excluding productions with a terminal in them, and mark $A_i$ as nullable if all $B_i$ are nullable. We keep doing this loop until we finish a loop without marking any nonterminals as nullable.</p>

<p>My problem with this algorithm is that it has a $O(n^2)$ running time: a worst case is for instance $A_1 \rightarrow A_2$, $A_2 \rightarrow A_3$, $A_3 \rightarrow A_4$, ..., $A_{n-1} \rightarrow A_n$, $A_n \rightarrow \epsilon$.</p>

<blockquote>
  <p>Is there an algorithm for this problem
  with a better running time than
  $O(n^2)$?</p>
</blockquote>

CC BY-SA 2.5
2010-10-26T17:25:38.180Z
Isn't it elementary to implement that algorithm in linear time? Might this be a homework problem?
Warren Schudy
CC BY-SA 2.5
2010-10-26T17:31:47.377Z
Are you interested in a certain class of grammars or do you want to tackle arbitrary grammars?
Raphael
CC BY-SA 2.5
2010-10-26T23:16:00.297Z
I'm interested in tackling arbitrary grammars: I'm implementing an Earley parser, for which it is useful to know if a nonterminal can derive the empty string. My initial reaction was that this should be trivially solvable in linear time, but grammars like $A \rightarrow B$, $B \rightarrow A$ complicate matters.
Alex ten Brink
CC BY-SA 2.5
2010-10-27T20:07:03.140Z
Do you have a reason to keep such rules in any practical situation?
Raphael
CC BY-SA 2.5
2010-10-27T20:58:39.007Z
I'm implementing an Earley parser in the manner described here: http://webhome.cs.uvic.ca/~nigelh/Publications/PracticalEarleyParsing.pdf. In the approach taken in that paper, at some point one needs to find the nullable nonterminals for a grammar: once these are known it's very easy to adapt the Earley algorithm to handle epsilon productions.
Alex ten Brink
<ds.algorithms><fl.formal-languages><time-complexity>
Quickly finding empty-string producing nonterminals in a CFG
Alex ten Brink
# Quickly finding empty-string producing nonterminals in a CFG

(Asked by: username_0 on 2010-10-26)

For a given context free language G, we call a nonterminal $A\_i$ *nullable* if $A\_i \rightarrow^\* \epsilon$, ie we can derive the empty string from $A\_i$ after applying a finite number of productions.

There is a simple algorithm for determining which nonterminals of a grammar are nullable as can be found [here](http://www.math.grin.edu/~rebelsky/Courses/CS362/2004S/Outlines/outline.16.html):

We start by considering all nonterminals as not nullable. We mark all $A\_i$ as nullable if there is a production $A\_i \rightarrow \epsilon$. We then loop over all other productions $A\_i \rightarrow B\_1 B\_2 \dots B\_k$ excluding productions with a terminal in them, and mark $A\_i$ as nullable if all $B\_i$ are nullable. We keep doing this loop until we finish a loop without marking any nonterminals as nullable.

My problem with this algorithm is that it has a $O(n^2)$ running time: a worst case is for instance $A\_1 \rightarrow A\_2$, $A\_2 \rightarrow A\_3$, $A\_3 \rightarrow A\_4$, ..., $A\_{n-1} \rightarrow A\_n$, $A\_n \rightarrow \epsilon$.

> Is there an algorithm for this problem
> with a better running time than
> $O(n^2)$?

**Tags:** ds.algorithms, fl.formal-languages, time-complexity
> **Comments:**
> **username_1**: Isn't it elementary to implement that algorithm in linear time? Might this be a homework problem?  
> **username_2**: Are you interested in a certain class of grammars or do you want to tackle arbitrary grammars?  
> **username_0**: I'm interested in tackling arbitrary grammars: I'm implementing an Earley parser, for which it is useful to know if a nonterminal can derive the empty string. My initial reaction was that this should be trivially solvable in linear time, but grammars like $A \rightarrow B$, $B \rightarrow A$ complicate matters.  
> **username_2**: Do you have a reason to keep such rules in any practical situation?  
> **username_0**: I'm implementing an Earley parser in the manner described here: http://webhome.cs.uvic.ca/~nigelh/Publications/PracticalEarleyParsing.pdf. In the approach taken in that paper, at some point one needs to find the nullable nonterminals for a grammar: once these are known it's very easy to adapt the Earley algorithm to handle epsilon productions.  

---

## 1 answers

### Answer by username_1 on 2010-10-26. Score: 10 | Accepted answer

Can't one implement that algorithm in linear time as follows? (Warning I haven't proof-read this too carefully, so bugs are likely.)

In what follows whenever I say "production" I mean to include only those that include no terminals.
Build a list, for each non-terminal, of the productions it appears in. For every production $i$ let $c\_i$ count how many distinct non-terminals in the right hand side are currently marked non-nullable. Let $Q$ denote a queue of non-terminals that have been marked nullable but not yet processed. Initialize all $c\_i$ to the number of distinct non-terminals in the right hand side of production $i$. Initialize all non-terminals to not nullable. For every non-terminal $Z$ generated by production $i$ with $c\_i=0$ add $Z$ to $Q$ and mark $Z$ as nullable.

While $Q$ is non-empty, remove an arbitrary non-terminal $X$ from $Q$ and process it as follows. For every production $j$ that $X$ is in, decrement $c\_j$. If a $c\_j$ becomes zero, check to see if the corresponding non-terminal $Y$ has been marked nullable already. If not, mark $Y$ nullable and add $Y$ to $Q$.

> **Comments:**
> **username_0**: Unless I'm missing something I think your algorithm should work. I just find it very odd that if I search the internet for an algorithm for this problem, I get over half a dozen hits on the first page describing some variation of the algorithm I described in my first post - why give a n-squared algorithm if a simple linear algorithm exists?  
> **username_1**: One likely reason for giving the quadratic algorithm is that it's even simpler. If you just want to give people an understanding of nullability hiding implementation details makes sense.  

---

