Erasing Performed by Scattered Context Grammars

Abstract

A scattered context grammar, G, erasesnonterminals in a klimited way, where k ) 1, if for every sentencebelonging to G's language, there is a derivation such that in every sentential form, between every two symbols from which G derives non-empty strings, there is a string of no more than k nonterminals from which G derives empty words. This paper demonstrates that any scattered context grammar that erases nonterminals in this way can be converted to an equivalent scattered context grammar without any erasing productions while in general, this conversion is impossibie.

Keywords

• scattered context grammars
• erasure of nonterminals

-

This paper discussesscattered context grammars, which representan important type of semi-parallel grammars (see [ 1-4,6-8, 12, 13 ]). It concentratesits investigation on the role of erasingproductions and the way they are applied in these grammars. While scattered context grammars with erasing productions characterize the family of recursively enumerablelanguages,the same grammars without erasing productions cannot generateany non-context-sensitivelanguage(see [ 3,4 ]).As aresult, in general,we cannot convert any scatteredc. ontext grammar with erasing productions to an equivalent scattered context grammar without these productions. In this paper, we demonstrate that this is always possible if the original grammar ero$es'its nonterm'inals in a k-lim,ited,way, where k is a positive integer; for every sentencethere is a derivation such that in every sentential form, between any two symbols from which the grammar derivesnonempty strings, there is a string of no more than k nonterminals from which the grammar derives empty strings later in the derivation. Consequently,the scattered grammars that have erasing productions but apply them in a k-iimited way are equivalent to the grammars that do not have erasingproductions at all.

In [ 3 ] it was demonstrated that a language generated by propagating scattered context grammars is closedunder restricteclhomomorphism. Note that our <iefinitionof ft-lirniteclerasingdiffers significantly from the rvay how symbols r:a' be erasedusing restricted homomorphism. While in caseof restricted homomorphism a ianguagecan be generatedby a propagating scattered context grammar in case that at most k symbols are deleted between every two terminals in a sentence,in caseof a scattered context grammar which erasesits nonterminals in a k-limited way virtually unlimited number of symbols can be deleted between every two terminals in a sentencein casethat during the derivation processbetween two non-erasablesymbols there is a string of at most k erasabiesymbols. Therefore, the result presented in this paper representsa generalization of the previously published result.

Preliminaries

We assumethat the reader is familiar with the languagetheory (see[ 5,9-11 ]). For an alphabet, V, card(V) denotes the cardinality of V. I/* represents the free monoid generated by I/ under the operation of concatenation. The unit of V" is denoted by E. Set I/+ _ V* - {e}. For ru € V*, l.l and alph(tr) denote the length of ru and the set of symbols occurring in tcr,respectively.For L g V - , a l p h ( t r )- { a : a € a l p h ( u ., 'w) € L } . L e t p o s ( a 1.. . a i . . . a n , i ) : a i f o r 1 < i 1 n , a 1 . . . a n € V + .

A contert-free granxmar (see [ 5 ]), a CFG for short, is a quadrupl€, G : ( V , T , , P , S ) ,w h e r eV i s a n a l p h a b e t ,T g V , S e V - ? , a n d P i s a f i n i t e s e t o f productions such that each production has the form A -+ r, where A e V - T, r e V*. Let lhs(,A ---',) and rhs(A --* r) denote A and r, respectiveiy.If A --, r e P, u,: r'As,,and u : Trs) where r,s € I/*, then G makesa deriuation step from uto u accordingto A , tr) symbolicallywritten as u + ulA --- r] in G or, simply, u * u. Let =++ and +* denote the transitive closure of =+ and the transitive-reflexive closure of +, respectively.The languageof G is denoted by L(G) and defined as L(G) -- {r : r e T* , S =+* ,}.

3 Definitions and Examples

The core grarnrnar underlying a scatteredcontert grammar, G : (V,,7, P, S), is denoted by core(G) and defined as the context-free grammar core(G) : ( V , , T , c f ( P ) , , S )w i t h c f ( P ) - { B - + y : B - - - A e p ( p ) f o r s o m ep e P } . L e t ' U : ' t 1 , r A 1 U 2 A 2 . . . " u , n A n u n * l : * U 1 T 1 U 2 I 2 . . . ' t - t , n f r n ' t l n - y:1 W [ ( A t , . . . , A n ) (rt,...,rn)l in G. The part'ial m-step contert-frees'imulat'ionof this step by core(G) is denoted by pcf,n(, =+ u.') and defined as core(G)'s m-step derivat i o n o f t h e f o r m u t A t u z A z . . . u n A n L t n + r* u 1 r 1 u 2 A 2 . . . u n A n u n . * =l ) + U1tyu2t2 . . .LLrtx)rn'um.*IArn.+.t. unAnurrll wherem 1n. The contert-frees,imulation is a special caseof the partial rn-step context-free simulation for rh : TL, denoted by cf (u + w). Let u : 't)t1* yn: tl be a derivation in G of the form u t * u z ) u s - * . . . + u r r .T h e c o n t e x t - f r e e s i m u l a t i o nyo)f* w b y c o r e ( G )i s denoted as cf (u +* w) and defined as u1 =)* u2 )* u3 ==)* . . . +* u' such that for all 1 S i 1 n - t, tLi+* ur.'1 in core(G) is the context-freesimuiation of ut ) u r 1 1i n G . L e t ^ 9+ * r i n G b e o f t h e f o r m , S + * u A u + * r . L e t c f ( , S= + . r ) i n core(G) be the context-free simulation of ,S +* r in G. Let I be the derivation tree corresponding to S +* r in core(G) (regarding derivation trees and related notions, we use the terminology of [ 5 ]). Consider a subtree rooted at .4 in t. If the frontier of this subtree is e, then G erasesA in ,9 +" uAu 1* a, symbolically written as L, and if this frontier cliffersfrom e, then G d,oesnot eraseA during t h i s d e r i v a t i o n s, y m b o l i c a l l yw r i t t e n u r , 4 . .I f w - A , . . . A n o r , : A , . . . A n , we write A or rl, respectively.Let G : (V,T,P, S) be a SCG, and let k > 0. G eT-aseists nonterm'inals in a k-li,mi,tedway if for every y e L(G) there exists a derivation ,5 =+* y such that every sentential form r of the derivation satisfies the following two properties:

1. Every r: uAuBw,, A, B, il, satisfieslrl < k.

2. Every r:uAu, A, satisfiesi:f [t"or it, then lul ( k or lrl S ft, respectively. Eramples 1. Observethat the grammarGt : ({^9,,48,, C, A', 8', C', a,b,c,A}, {o,,b,c,U}, { ( S ) * ( A B C ) , ( 1 ) * ( a A A ' ) , ( B ) * ( b B B ' ) , ( C ) - ( c C C ' ) , ( A , B , , C ) ( A , y , A ) , ( A ' ,B ' , C ' ) t ( y , A , A ) \ , , S )g e n e r a t e st h e l a n g u a g e, L ( G 1 ) - { o n ,n-rrbnyn*Lrnrn*r : n ) 0). Therefore,there does not exist any restricted homomorphism h such that h(L(Gr)) - {anbncn : n } 0}. However, as demonstrated by the following example, there exists a scattered context grammar which erasesits nonterminals in a k-limited rvay. 2 . O b s e r v et h a t t h e g r a m m a r G 2 : ( { S , A , B , , C , A ' , , 8 ' , C ' , e , b , " } , { a , b , c } , { ( S ) - ( A B C ) , ( A ) * ( a A A ' ) , ( B ) - ( b B B ' ) , , ( C )- ( c C C ' ) , ( A , B , C ) (s,e, e), (A' , B' ,C') --+ (e, e,e)),,S) generates the language L(Gz) : { a " b ' c n : n } 0 } . A s t h e d e r i v a t i o no f a n y s t r i n g a a . . . a a b b . . . b b c c . . . c c e L(Gr) *oy be of the form .9 + ABC +* aAAtbBB'cCC' + aAbBcC +" aaAA'bbBB'ccCC' + aaAbbBccC 1* ss . . . aaAA'bb . . . bbBB' cc . . . ccCC' + a ( r .. . L t o , A b.b. b. b B c c . . . c c C. + a a . . . a a l t b . . . b b c c . . . c c .

the grammar erasesits nonterminals in a 2-limited way. 3 . C o n s i d e trh e g r a m m a rG 3 : ( { S ,A , B , A ' , 8 ' , a , b , c } , { o , b , . } , { ( S ) - - ( A A ) , (A, A) --- (aA, A' A), (A, A) ---'(8, B), (8, B) * (bBc,B' B), (8, B) -* (e,e), ( A ' , 8 ' ) * ( € , € ) ) , S ) . O b s e r v et h a t L ( G s ) : L ( G 2 ) . H o w e v e r ,b e c a u s et h e fi.rst part of every derivation has the form , 5 + A A +

a A A ' A + a a A A ' A ' A + * a a . . . a A A ' A ' . . . A ' A and ail A"s are deletedin the secondpart of the derivation, there does not exist any k such that G3 erasesits nonterminals in a k-limited way. 4

Results

The main result of this paper follows next.

Theorem 1. For euery SCG, G, whi,ch,erasesits nontertn'inalsin a k-limi,ted way there eristsa PSCG, G, such that L(G): L(G).

Proof. Let G : (V,T,e S) be a SCG which erasesits nonterminais in a kl i m i t e dw a y .F o r e v e r yp : ( A t , . . . , A i , . . . , A n ) * ( r r ) . . . ) r i , . . . , r n ) € P l e t l _ p , i Jd e n o t eA i , t r i f o r a l l I < i l n . L e t t I ' / - { l p , i ) i p e P , L < 1 , 1 n ( p ) } a n d Z ' : { l p , i ) t : I p , , i ) € f } . S e t l i r : { ( " ) : r e ( V - f ) . u ( V - T ) . T ( V ? ) - , 1 " 1 < 2 k + U . F o r e v e r y ( " ) e l / 1 a n d l p , i ) € P , d e f i n e

l h s - r e p l a c " ( ( ",)L p , i ) ) : { ( * r l _ p , i ) r r ) | r y , n 2 € V * , r 1 l h s ( l p , i ) ) r , - r } . Set .n/z: {(r) ' (r) - lhs-replace((y,l)p,i,)),(g) € I/r,lp,i) e V}. For every (") e fi1 and l&,i,J' e V', define

i n s e r t ( \ r ) , l p , i ) ' ) : { ( r , l p , i ) ' * r ) ; n 1 , 1 2e V " , r t t 2 - r } .

S e t A { : { ( " ) ' ( r ) - i n s e r t ( y ) , l p , i ) ' ) , ( i l € l / r , l p , i ) ' € / ' } . F o r e v e r y r : (rr)@r). . . (r,,) € (Nt U,^/2U lq). for somen 2 I, define

For every r € 16 U li2 U /V;, defi.ne

Set 7 : T u l/r U lf2 U NrU {S}. nenne the PSCG,,

j o i n ( r ) : r r 7 2 " ' t r n ' s p l i t ( r ) : { a ' . t r : j o i n ( y ) } .

G : ( V , T , P , S ) , with P constructed as follows: 1. For every p: (,9) -' (r) e P, add ( S )- ( ( L pt,l ) ) t o P ; k-Limited Erasing Performedby ScatteredContextGrammars 2 . F o r e v e r y ( " ) e f i 1 , e , r e r yX € i n s e r t ( ( r ), l p , n ) ' ) , w h e r e p e P , r ( p ) - n , e v e r y ( g ) e . | y ' 1a, n d e v e r y Y e l h s - r e p i a c e ( ( y ) , L q , l . J w),h e r e q € P , a d d ( u ) ( X , \ a ) ) - - ( ( " ) , Y ) , a n d ( b ) ( ( y ) , X ) - - ( ) ' , ( r ) ) t o P ; ( " ) i f ( z ) : ( y ) , a d d

( X ) - ( Y ) t o P ; ( d ) ( x ) * ( ( ' ) ) t o P ; 3 . For every (") e N1, every X € insert((r), l-p,i)'), where p e P, i < n(p), e v e r y ( a ) e l y ' 1 ,a n d e v e r y Y e l h s - r e p l a c e ( ( A ) , I _ p+, i 1 l ) , w h e r e q € P , a d d ( u ) ( X , ( i l ) - ( ( r ) , Y ) t o P ; ( b ) i f ( r ) : ( y ) a n d p o s ( X ,l ) : l p , e l ' , p o s ( Y ,m ) : l _ p , +i 1 ) ' , 1 ( m , a d d ( X ) - ( Y ) m P ; +A . F o r e v e r y( r t l p , i ) r r ) € l h s - r e p l a c e ( ( z ) , l p , i ) )(," ) € l / r , l p , i ) € V , 1 1 , 1 2 e I / * , a n d e v e r y Y e s p l i t ( r 1 r h s ( l p , i ) ) l p , ' i , ) ' * r ) , a d d ( ( r t l p , i ) r t ) ) * ( Y ) t o P ; U . For every o € 7, add

( ( o ) ) - ' ( r z )t o P Denote the set of productions introduced in step i of the constructionby iP, f.or 1 < i < 5 .

L e t , 5 + * A 1 * v 1i n G , w e L ( G ) , A e ( l / r U l / 2 U l f i ) . , a n d l e t f o r e v e r y (t) e alph(y) there exist 1 . A e a l p h ( z ) s u c h t h a t A o r 2 . l - p , i . )e a l p h ( z ), l p , i ) € t I / ,A : l h s ( l p , i ) ) s u c h t h a t 1 . .

Then we write !.

Basic ldea. G simuiates G by using nonterminals of the form (. ) In each nonterminal of this form, during every simulated derivation step, G records a substring of the corresponding current sentential form of G.

The nrle constructed in (1) only initializes the simulation process.By rules introduced in (2) through (4), G simulates the application of a scattered context rule p from P in a left-to-right way. In greater detail, by using a rule of (2), G nondeterministically selectsa scattered context rule p from P. Supposethat p c o r r s i s tos f c o n t e x t - f r e er u l e s r r , . . . , T i - ; . t T i ; . . . , T n . 8 y u s i n gr u l e so f ( 3 ) a n d (4), G simulates the application of 11 through r,, one by one. To explain this in grea[er detail, supposethat G has just completedthe simulation of ri-1. Then, to tire right of this simrrlation, G selectslhs(r,) by using a rule of (3). That is, this selectionis mtrde inside of G's nonterminal in which the simulation of ri-1 has been performed or in one of the nonterminals appearing to the right of this nonterminal. After this selection,by using a rule of (a), G performs the replacementof the selectedsymbol lhs(ra) with rhs(r;).

If a terminal occurs inside of a nonterminai of G, then a rule of (5) allows G to changethis rronterminalto ihe ternrinal string containedin it. R'igorousProof. (Due to the requirements imposed on the length of this paper, the formai proofs of the foliowing three lemmas are omitted.) Lemma 1. Euery successfulderiuati,onin G can be erpressedin the followi,ng way:

S * e ( L pl,J ) [ p ' ] *h u t@l + E , [ o ] , 1 r r , . . . t u n * r€ V * , A t , . . . , A n € V - 7 , A t - l h s ( l , p , L ) )p, e P , a n d { u 1 ;t h e n , euerypartial h-step contert-free simulation pcfn() : ut At uzAz . . . LrnAnuryl

4 C u t f r 1 u 2 v 2 .. l - L n t n t l n a 1 l p : ( A t ) . . . ) A , . ) * ( * r , . . . , r r ) ] ) of the forrn

uyAlu2AzusAs . . .'u,rAnu,n+:1 ) + c o r e ( G u) 1 r y u 2 A 2 u z A z . . . u n A n u n l 1 +core(G) U1ix1U2T2uSA.S. .'u"nAntr,nrr1 *3*j,", uyTlu2t2usts . . . u7rlun+tAn+r . . . unAnungl l A t * r t l [A2 --- r2] i,s perforrned in core(G) i.f and only i,f

U 1 +6 w', lpi) *6 rrr2 lpSl +6 tu'2tptl * T - u i +6 w6 tpt^l =+6 uL lph) is perfortneid,nG, whereptr,.. .,p37e, rP, pt,. . .,ph € ap, and, w\ e split(u1rrLp,1.1'uzA.,. .r.l,rAnltn+i), Ixz€ split(u1 rtuzlp,2) . . . unAnun-.,r1), w; € split(u1z 11.12.x21p,.2.).' unAnun+t), w t r € s p l i t ( u 1 i 8 1 u 2 f i 2 . . u h l p , h ) u n + t A n + t . . . " u , , r A , 5 . l , .)+, t u)',,e split(u1r tuzfiz . . . uhrhl_p,h| uh+rAn+r . . . unAnu,,+i); i r r ,a d t l i t i o n , e u e r y w e { w 2 ) . . . , , w n , w | ) . . . ) w ' n } s o " t z s f , efis. Corollary

1. The result from Lemma 2 holdsfor a context-frees'imulati'on. Let for some p e P.Then, - denotes the simulation of this d.erivationstep in G as shown in Lemma 2 and Corollary 1. We write ur1 - *; lp), or, shortly, ur1 utl. Therefore, ,, *'t-1 tll from Lemma 2 is equivalent to u1 ---'w;. L e m m a 3 . L e t 1 1 Q . V * a n d n ' , e s p l i t ( r / tr l p r , I ) " i ) , : r,rt fp, 1l e V, and fr'r; then euery deriuat'ion w l t e r er " r l h s ( l - p t , I ) ) r ' t , is performed tn G if and only i,f

.tJ I * c r z for all I < i < m, 2 S j I m, and

r ' , n + r € s p l i t ( r i r n * l ) 1 l - p m + r , , I ) r ' p n + t 1 )w i t h r m * r # T * , U I

I i n + t e spiit(r,,r..y) with rm*r e T* ,

where r,i,rriz - Ti for all I < i < n r , / i r l h s ( [ p ; . r ) ) r ' i z : m * L , a n d e u e r yi € { r 1 , . . . , I- r r t , I-', 2 r . . . , I- }t n * l j \ s a t. ? ^-s f l ' eI=s. x i f o r a l l 2 S j S Flom Lemma 1,

S * e ( L p1, l) . Ar (Lp,tl) e split(Lp1, J),S - lhs(fio1, .1)G,'ssimulationasdescribeidn Lemma 3 can be performed,so

(Lpl,J) =+b, lal, where @is a sequenceof productionsfrom 2PUsPU4P.If. a successfudlerivation i s s i m u l a t e dt,h e n w e o b t a i n u - - ( o r ) ( o r ). . . ( o " ) , f r ) L , a t , a 2 , . . . , a n € T . Finally, by the application of productions from 5P we obtain

u + [ u , where u : ara2 . . . orr.Therefore, for every SCG, G, which erasesits nonterminals in a k-limited way there exists a PSCG,G, such that L(G) : L(G). ! Thi,s work was supported, by GA1R grant 102/05/H050 and' FRVS grant FR762/2007/G 1.

References

1. H. Fernau . Scattered context grammars with regulation . Annals of Bucharest Uniu ., M ath.-Informatics Series, aSQ): aI- ag , 1996 .

2. J. Gonczarowski and IvI. K. Warmuth . Scattered versus context-sensitive rewriting . Acta Infomnatica , 27 : 8I - 95 , 1989 .

3. S. Greibach and J. E. Hopcroft . Scattered context grammars . Jountal of Computer and System Sci , ences3 ,: 233 - 247 , 1969 .

4. A. Meduna . A trivial method of characterizing the family of recursively enumerable languagesby scattered context grammars . EATCS Bulletin , 56 : 104 - 106 , 1995 .

5. A. Meduna . Automata and Languages: Theory and Applications . Springer-Verlag, London, 2000 .

6. A. Ivleduna . Generative power of three-nonterminal scattered context grammars . Theoretical Computer Sc'ience , 237 : 625431 , 2000 .

7. A. Nleduna and J. Techet . Generation of sentenceswith their parses: the case of propagating scattered context grammars . Acta Cyberneti"ca,17:LI-20 , 2005 .

8. D. Ivlilgram and A Rosenfeld . A note on scattered context gramrnars . Information PrutcessingLetters , 1 : 47 - 50 , 1971 .

9. G. E. Revesz . Introduction to Forrnal Language Theorg . McGraw-Hill , New York, 1983 .

10. G. Rozenberg and A . Salomaa, editors. Handbook of Formal Languages ,volume 1 through 3. Springer-Verlag, Berlin, 1997 .

11. A. Salomaa . Formal Languages.Academic Press,London, 1973 .

12. G. Vaszil. On the descriptional complexity of some rewriting mechanismsregulated by context conditions . Th,eoreticalComputer Science , 330 : 361 - 373 , 2005 .

13. V. Virkkunen . On scattered context grammars . Acta Uniuersitat'is OuLuensi ,s, SeriesA, Ivlathematica6: 75 - 82 , 1973 .