1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – Hendrik Jan Jun 1 at 18:38
-1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – J.Ober May 31 at 23:56

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.