# What is appearance checking in the context of formal grammars?

As I did not find any definition of the term "appearance checking" although it is widely used, I am eager to ask as what it can be defined. Perfect would be an example using a context free grammar.

Appearance checking is a concept in the theory of regulated grammars.

In an ordinary (context-free) grammar we may appay a production to a string if its right-hand side occurs in that string. So for $$\pi: A\to \alpha$$ we write $$x \Rightarrow_\pi y$$ if $$x= w_1 A w_2$$ and $$y = w_1\alpha w_2$$.

In a regulated grammar we may specify the order in which the productions should occur in the derivation. As an example, the following context free grammar

$$\pi_0: S\to AC$$, $$\pi_1: A\to aAb$$, $$\pi_2: C\to cC$$, $$\pi_3: A\to ab$$, $$\pi_4: C\to c$$

generates the language $$\{ a^nb^nc^m \mid m,n\ge 1\}$$. As a regulated grammar we can choose to restrict the sequences of chosen productions to be the (regular) language $$\pi_0(\pi_1\pi_2)^*\pi_3\pi_4$$. Clearly with this restriction the grammar generates the non context-free language $$\{ a^nb^nc^n \mid n\ge 1\}$$.

Appearance checking is the notion that we are allowed to skip a production if it cannot be applied. Formally for $$\pi: A\to \alpha$$ we write $$x \Rightarrow^{ac}_\pi y$$ if either (i) $$x$$ contains $$A$$ and $$x \Rightarrow_\pi y$$ or (ii) $$x$$ does not contain $$A$$ and $$x=y$$.

How it this useful? It can be used to check that actually all symbols in the string are rewritten before the derivation continues. Consider the productions $$\pi_1: A\to BB$$, $$\pi_2: A\to X$$, $$\pi_5: B\to a$$ and the "regulator" $$\pi_1^*\pi_2\pi_5^*$$, and starting with the string $$A^n$$. In this case the variable $$X$$ cannot be rewritten. So applying the production $$\pi_2$$ has to be avoided. This is allowed in appearance checking mode when $$A$$ does not occur in the string. That means we have to rewrite all $$A$$'s into $$B$$'s, then we can skip $$\pi_2$$, and continue rewriting the $$B$$'s. This trick can be extended into a grammar that generates $$\{a^{2^n} \mid n\ge 0\}$$:

$$\pi_1: A\to BB$$, $$\pi_2: A\to X, \pi_3: B\to A$$, $$\pi_4: B\to X, \pi_5: A\to a$$ and "regulator" $$(\pi_1^*\pi_2\pi_3^*\pi_4)^* \pi_5^*$$

Informally we repeat the following. First $$\pi^*_1$$ doubles the number of $$A$$ (temporarily renaming them into $$B$$'s). We have to rewrite all $$A$$'s as otherwise we have to apply $$\pi_2$$ and this will introduce $$X$$ a letter that cannot be rewritten, so in that case the derivation will not be successful. Similarly $$\pi_3^*\pi_4$$ will rename all $$B$$'s into $$A$$'s effectively doubling the $$A$$'s. In the final round $$\pi_5^*$$ renames all $$A$$'s into the terminal symbols $$a$$.

• I have tried to add some informal explanation. Note that $X$ is essential. If no $A$'s are present we can skip $\pi_2$, otherwise we are forced to apply $\pi_2$ by the regulator and $X$ is introduced. As we cannot rewrite $X$ the derivation cannot be successful. Application of $\pi_2$ signals failure to rewrite all $A$'s. Without appearance checking there is no way to force this. – Hendrik Jan Jun 1 at 18:38

A quick google search gave me this. The definition 2 seems to be what you want.

• Thank you for the quick answer. Actually I was reading that paper before asking here but did not understand that definition. My bad I guess, but a simplified example would be worth gold. – J.Ober May 31 at 23:56