Scattered Context Grammars research

!!! WORK IN PROGRESS - Please do not read - and I'm serious about it :-) !!!

Introduction

Scattered context grammars were introduced by S. Greibach and J. Hopcroft in 1969 as a straightforward generalization of context-free grammars. Each production of these grammars contains n context-free productions which are applied in parallel to the current sentential form. For example a scattered context production

$(A, B, C) \rightarrow (a, b, c)$

which consists of three context-free productions,

$A \rightarrow aA, B \rightarrow bB, C \rightarrow cC$ ,

is applicable to the sentential form $aAbBcC$ so that all context-free components are applied in parallel and the nonterminals on their left-hand sides are in the same order as they appear in the sentential form. As a result,

$aAbBcC \Rightarrow aaAbbBccC$ .

It is easy to see that by adding productions

$(S \rightarrow ABC)$

and

$(A, B, C) \rightarrow (a, b, c)$ ,

where $S$ is the start symbol of the grammar, we can easily describe the non-context-free language

$\{a^nb^nc^n : n \geq 1 \}$ .

The first advantage of scattered context grammars can be seen here - by using several context-free productions in parallel, we are able to describe some context-sensitive languages. Furthermore, by only extending context-free grammars, which are well studied and used in many practical applications, we preserve the simplicity of language description. In addition, for modeling context dependencies which span over the whole sentential form (for example in the above example), the description is much simpler than when using ordinary context-sensitive grammars.

Basic Definitions

Formal Languages

The reader is expected to be familiar with the basics of formal language theory. This section is intended to describe the used terminology rather than to explain the basics of formal language theory.

An alphabet V is a finite nonempty set, whose members are called symbols. The cardinality of V, |V|, is the number of V's members. A finite sequence of symbols from V is a string or, synonymously, a word over V; specifically, $\epsilon$ is referred to as the empty string. The length of a string x ∈ V ^*, denoted by |x|, is the number of elements in x. For U ⊆ V, |x|_U denotes the number of occurrences of elements from U in a string x. By $V^*$ , we denote the set of all strings over V; $V^+ = V^* - \{\epsilon\}$ . Any subset L ⊆ V^* is a language over V. By $alph(x)$ we denote the set of all symbols occurring in a string x. Set

$alph(L) = \bigcup_{x \in L}{alph(x)}.$

Let x,y &isin V^* be two strings over an alphabet V. The concatenation of x with >y, denoted by xy, is the string obtained by appending y to x. For all i ≥ 0 the ith power of x, denoted by $x^i$ , is recursively defined as (1) $x^0 = \epsilon$ and (2) $x^i = x x^{i-1}$ for i ≥ 1. The reversal of x, denoted by $rev(x)$ , is x written in the reverse order. Let L₁, L₂ ⊆ V^* be two languages over V. The concatenation of $L_1$ and $L_2$ , denoted by L₁L₂, is defined as

$L_1L_2 = \{xy : x \in L_1, y \in L_2\}.$

The right quotient of $L_1$ with respect to $L_2$ , denoted by $L_1 / L_2$ , is defined as

$L_1 / L_2 = \{y : yx \in L_1, \mbox{ for some } x \in L_2\};$

similarly, the left quotient of $L_1$ with respect to $L_2$ , denoted by L₂ \ L₁, is defined as

$L_2 \backslash L_1 = \{y : xy \in L_1, \mbox{ for some } x \in L_2\}.$

We also use a special type of the right and the left quotient. The exhaustive right quotient of $L_1$ with respect to $L_2$ , denoted by $L_1 // L_2$ , is defined as

$L_1 // L_2 = \{x : x \in L_1 / L_2, \mbox{ and no word in } L_1 // L_2 \mbox{ is a proper prefix of } x \};$

similarly, the exhaustive left quotient of $L_1$ with respect to $L_2$ , denoted by L₂ \\ L₁, is defined as

$L_2 \backslash\backslash L_1 = \{x : x \in L_2 \backslash L_1, \mbox{ and no word in } L_2 \backslash L_1 \mbox{ is a proper suffix of } x\}.$

References

(pdf) A. Meduna. Automata and Languages: Theory and Applications. Springer, 2000, pp. 920.

(pdf) G. Rozenberg and A. Salomaa. Handbook of Formal Languages. Springer, 1997, pp. 2051.

(pdf) A. Salomaa. Formal Languages. Academic Press, 1973, pp. 322.