ETOL Grammar Non-Emptiness

I had never heard of this type of grammar before.  Let’s see if I can explain it.

The problem: ETOL (or “ET0L”, with a digit 0 instead of the letter ‘O’) Grammar Non-Emptiness.  This is problem AL16 in the appendix.

Description: An ET0L grammar is a grammar consisting of:

  • A set of non-terminal symbols N
  • A terminal alphabet Σ
  • A start symbol S from N  (The paper that has the reduction allows a start string containing multiple symbols, but we can get that by having a start production S-> the start string)
  • Productions in this grammar are defined by a set P of tables.  Entries in the table map a symbol in N or Σ to a string in (N∪Σ)*

While multiple tables are allowed, our reduction will have just one table in P.

Given a grammar G, is the language it generates non-empty?

Example:  So, to get where we’re going in the reduction, it’s helpful to note that the main difference between this kind of grammar (especially with just 1 table) and a regular Context-Free grammar is that terminals are allowed to be on the left hand side of a production.  But we don’t have to use that property.

A grammar is empty if it never produces a terminal.  So, for example:

S->A
A->B
C->a
a->ab

..is empty because we can never get to the C production.

Reduction: The paper is by Jones and Skyum, and the reduction is from Regular Expression Non-Universality on one character alphabets.  This is Lemma 30 from that paper.  We’re given a regular expression R that came from the 3SAT production.  Recall that the expression we built looked like this:

\bigcup\limits_{k=1}^{n} \bigcap\limits_{j=2}^{p_{k}-1} [0^j \cdotp (0^{p_k})^*]

What we care about for our grammar is that there are n copies of an expression of the form 0^{p_i}0^{q_i *} (where i goes from 1 to n)

In the grammar we build, we have:

  • Symbols of the form Z_i^j, where i goes from 1 to n, and in each Z_i, the j runs from 0 to p_i + q_i -1
  • Z_1^{p_1} through Z_n^{p_n} are the non-terminals, everything else is a terminal.
  • Our start string is Z_1^0Z_1^0...Z_n^0
  • For every j except p_i + q_i -2 (the last one) we have the production Z_i^j \rightarrow Z_i^{j+1}
  • For the last j, we have the production Z_i^{p_i+q_i-1}\rightarrow Z_i^{p_i}

The paper asserts without really proving it that the language associated with this grammar is non-empty if and only if the expression we started with is not 0*.  I think this happens because we get 0* in the expression if one of the q_i values is non-zero.  If that happens, then the Z_i^{p_i+q_i-1}\rightarrow Z_i^{p_i} production isn’t a self-loop, and we can reach one of the terminal values.

Difficulty: 8.  I feel like I’m missing a lot of the point of the ET0L language by only using one table, but that’s what the reduction does.  I also wish I could confirm my explanation about why a non-empty grammar means the expression was 0*

 

Leave a Reply

Your email address will not be published. Required fields are marked *