terminal 
inal one 
need a 
context 
ly been 
xt free 
y due to 
es: they 
artificial 
1S. 
all: the 
le is the 
'e voice, 
wy of 
s derived 
mational 
orm by 
ved by a 
phrases: 
e river is 
ure, but a 
. Is often 
nensional 
raditional 
nensional 
leveloped 
nstead of 
: scholars 
cognition 
ed by the 
Onegin" 
strings in 
s, and the 
, and it is 
ppens in 
biguity is 
immars, a 
n-up type, 
operating 
e present, 
the string 
ley are not 
ir Kasami 
nplicity: it 
reduced to 
Actually, some procedures use simplified context-free 
grammars, based upon certain theorems, one of which 
being the so called Chomsky’s Normal Form Theorem 
(CNF): it states that a context free language may be 
generated from a grammar, so that the production rules 
shall have one of the following forms: 
A—BC, B and C being non-terminal symbols 
A a, a being a terminal symbol. 
For instance, let us make up the CNF, starting with the 
context-free grammar: 
S — bA S  aB A a 
B b A — aS B — 5S 
A bAA B — aBB 
Some well known algorithms may be used to convert a 
general context free grammar into a Normal Form 
according to Chomsky. 
Rules A — aand B — b should first be available in the 
canonical form. No rule exist in the form C — D, so 
(non terminal) variables can be directly substituted to 
terminal symbols, the first rewriting rule being thus 
substituted by both rules: 
S  CijA Ci b 
Therefore, the following substitutions take place: 
A — aS with A — CS C, a, 
S  aB with S — CiB C, a 
A-— bAAA with A — C3AA C, b 
B — bS with B — C5S C5 b 
B aBB with B 9 CG6BB C6 — a 
At last: 
A — C3AA, with A — C3Dj and 
B — C4qBB, with B — CD; and D, — BB 
Once a context free garmmar has been transformed into 
its Chomsky's normal forma, Kasami's table can be 
assembled, so that one can decide whether a string 
belongs to the said grammar. 
Be w= aja,....a, a string whose pertinence to a given 
gramamr is to be tested, the grammar being already 
reduced to the CNF. 
The algorithm is basically a triangular parsing table, 
whose elements are t; for 1 <i<nel <j<n-i+l. Every 
ti should have a value being a sub-set of N. The non 
terminal symbol shall be into t; if, and only if: 
A — ajdi4...di44. The string shall belong to the said 
language just in case S shall be found into t;,. 
The table is assembled as follows: 
=  onestates t; cA if A aj 
= one states t; =A even for a single k, such that 
| <k<j, if A BC is to be found in P, having B 
present in C and C in 1; Fk.j-k- 
Also, let us have the grammar: 
45 
S o AB, S > BC 
A — BA, A > a 
B CCBb 
Co AB,C a 
and the baaba string. 
The table which allows state whether the string belongs to 
the language generated by the said grammar is as follows: 
1 
  
  
  
  
  
) => 
|| |B AC AC B AC 
| S.A B S.C S.A 
0 B B 
0 SAC 
S,A,C 
  
  
  
  
  
  
  
Since S belongs to the case t;5, we may state that the 
string baaba is generated by the said grammar. 
4. Application test 
In order to evaluate how well such approach could be 
applied to the automatic interpretation of images 
(possibly for cartographic upgrading purposes or GIS 
geometric query) preliminary tests have been carried out 
onto simple geometric images. 
It is here shown an example addressed to draft a possible 
operational path for Parsing based pattern recognition of 
simple geometric entities. 
An appropriate test image has been created showing three 
different geometric figures: a rectangle, a scalene triangle 
and a equilateral triangle. The goal is to verify if the 
implemented grammar could correctly decide if one 
figure is or not an equilateral triangle. 
The recognition process goes on in the following way: 
>  apreliminary identification, based on 
radiometric/spectral discriminants, of the pixels of 
the image probably belonging to the searched 
objects is firstly carried out; 
> the selected pixels are then grouped in different 
distinct geometric entities using neighbourhood and 
region growing criteria (different colors in the image 
below); 
  
Fig. 1 Test image and polygon grouped pixels image. 
> for each entity a frame window is clipped from the 
orginal image and a  Fórstner filtering and 
thresholding algorithm is applied in order to select 
pixels most probably representing the vertices of the 
figure which has to be recognized;