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:
..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:
What we care about for our grammar is that there are n copies of an expression of the form (where i goes from 1 to n)
In the grammar we build, we have:
- Symbols of the form , where i goes from 1 to n, and in each , the j runs from 0 to
- through are the non-terminals, everything else is a terminal.
- Our start string is
- For every j except (the last one) we have the production
- For the last j, we have the production
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 values is non-zero. If that happens, then the 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*