This paper introduces deriuation table.sthat represent a complete grammatical derivations as whole in a vertical way. These tables are obtained by writing the consecutivesentential forms of grammatical derivations vertically one by one. The present paper places and discusses some restrictions on the columns of these tables. IVIorespecifically, these restrictions constrain the order of context-sensitive derivations on boundaries of columns. It is demonstrated, that grammars restricted in this way generate an infinite language hierarchy.
We assumethat the readeris familiar with the languagetheory (see[
Let V be an alphabet. 7* representsthe free monoid generated by 7 under the operationof concatenation.The unit of V is denotedby e. Set V+ : V* - {ui. For a word, w e V", ltll denotes the length of u. For a word of the form rtu, whererru) e V*,pref (r.): z denotesthe prefixof rw. Similarly,for a word of the forrrrtur, where r)u) e V*, then suf (wr): z denotesthe suffix of.wr.Let 1 t : a r a 2 . . . a r r .w h e r ea ; € V , I < i I n . T h e r e v e r s a ol f w , r e t s ( t u )i,s d e f i n e d a s r e u ( u ) : a ^ . . . . a 2 a r .
Throughout this paper, a phrase-structuregrammar, G _ (V,T,P,S). is
always specifiedin Kuroda normal form (see [
: : r : 1 I n l I n 2 . . . I n n t w h e r e m ) I ,t r f-iJ Q V * , t r i 1 r i 2 . . . r i r n : U i , l < i ( n a n d | < j I m . A s e g m e n t is every string rii in this table, and if rii € T*, rii is a term'inal segment. A colu'm' nis a vector of the form (rtj,rrj,..., rnj). Let a column of this fornt s a t i s f i ersL j : € , r z j : € , . . . , r k - I j : € , a n dl z p r l: 1 , l r x + t j l > 1 , , . . . , l r n j l> 1 , where 1 ( k ( , ' i + ' , T 2 3 + | ' . . . ' I n j * | ) b e t w o n e i g h b o u r i n g c o I u m n S ' f o r s o m e 7 > s u f ( r i i ) : A , p r e f ( r i i a r ) : B , s u f ( r i s 1 i ) : C , p r e f ( r , i y r r + t ) - D , A B - - ' , C D e P. Then, we say that AB --- C D is applied across the boundary between C1 and C2.
A flip-pushdownautomaton(see[
A confi,gu,rationof hI is any string of the form uApaw, where u € l*, A € f , p e Q, a.w € T* .If uApau and uuqw are two configurations and Apa -+ uq e R, then /Jy'nrakesa t'rartsit'ionfrom a configuration uApaw to u,uqut,symboiically written as uApausI uuqulApa ----u,q], or, simply, uApata ? uuqw.If q € A(p) and A - Zs, then uApaw I reu(u)Aqaw. It A + Zg, then uApau I Areu(u)qo*. The transition of this form performed by using of the mapping 4 is called the pushdown reuersal.Whenever, there is a choice between an ordinary pushdown transition or a pushdown reversal, then the automaton nondeterministically choosesthe next move. As usual, the n-fold product, the transitive closure On Vertical Grammatical Restrictionsthat Producean [nfinite LanguageHierarchy and the reflexive-transitiveclosureof F is denoted by F', F+ and F*, respectively, where n 2 0. Consider that cl I c2 | ... F cn,in IvI, n ) 0. Then, cn 1 . . . ) cz -l c1 is the same sequenccof moves in IvI written in reversal. We use this notation for maximal lucidity in some cases.Relations -1+ and -l* are defined in the usual way.
Let ft be a natural number. For a flip-pushdown automaton, fu|, we dcfine
the language accepted by final state and exactly k pushdown reversals to be
Lk(A'l) : {, e T*lZsqsw l. 7f with exactly k pushdown reversals,for any
1 € f* and / € Fi. Denote the family of context-free languagesand the famiiy
of recursively euumerabie languagesas CF and RE, respectiveiy.Next, denote
the fanrily of languages accepted by flip-pushdorvn autornata with exactly k
pushdown reversals as FPDA,6 and name every language from this family *
a k-fl"ipping language.From [
Theorem 1. A languageL is (m-1)-fii,pping i,f and only if there is a constant k > 1 and a graTnTnarG : (V,7, P, S) r'n Kuroda normal forrn, such that L : L(C) and G can generateeueryz € L(G) bu a deriuat'ionof the form ' : : : : : : :
: : : ) r n r T r t 2 . . . r n n , wheren)m are two pos'itiue'integersa, nd 1 . l r , t l S k , l < i { n , 1 < j < m 2 . f o ' ra l l h : 2 , . . . , m t h e r ee r i s t s r r h e V + s . u c h t h a t f o a'rl l q - 1 , . . . , h a ' n d " o : h * 1 , .. . , T r L T, q o : € 3 . J o ' ru l l a d j a c e ' rst "etg r r t e n t s r ra4' n r l r r 4 . , r 1 , , w h eI ' Sr' ec 1 n a ' n d d : I , 2 , . . . j m I, if thereis a rule that rewritesr"6r"d+t oTLboundaryin a contert way, then thereis no rale that rewrites anArpqrpq+r on boundaryin a contert way for a l l , ' J- -t c , c } 1 , . . . , ' n o , n dQ, : d + I , d * 2 , . . . , ' r n Proof. The onhl i/ portion is trivial. Next, we prove the i,f portion. That is, iet G be a gramlnar satisfying the conditions describedin Theorem 1. We construct a flip-pushdorvrarutornaton, M : (Q,7, l, R.,qo,Zo, A,,F) in the following way: . Q : { / } u { ( ' { , o ) l ( A , o+) f , A € N , a € V " , l o lS f r } r l : f g u { Z o , Z p } ,w h e r ef3 : { @ B - - .C D ) I A B . - .C D e P } . s _ ( S , r ) o ft: Rrru U RcstU RcszU.Rr U Rrtnao URr is constructedby performing following steps:
I For every r e T* with lrl < k
add rules of the form Zo(X,e)r ---+Zp(X,r) into 87 iI For every r eT* with l"l ! k and for every p : AB'-- CD e P add rules of the form (p)(X,e)r '-- (p)(X,z) into Rr III For cvery a,€ T u {e } and rule A -+ a,e P add rules of the form Z (X, aa/) "- Z (X, aA/) into Er1', where Z e f , Z * Zo and laapl > 0 IV For every AB '-- C D in P add: ( o ) Z p ( X , a C ) - - - ( A B - . C D ) Z p \ X , o ' A ) i n t o - R 6 : s 1 ( b ) ( A B - - - C D ) ( X , D P ) - ( X , B p ) i n t o R c s z (.) Z(X,aCDB)--- Z\X,aABB) into Rr,r,',where Z e f ,,Z * Zo V For every A -+ BC in P add: (o) Z(X,aBCp) -, Z\X,aA|) into R71',where Z e f , Z # Zo ( b ) Z p ( A , B ) - Z p ( C , e ) i n t o R n P , q , o V I F o r e v e r y ( X , t ) € Q , w h e r eX € l / s e t A ( ( X , e ) ) : { ( X , t ) } VIi For every A € l/, add Zp(4, A) '-- ef to -Rp
Tlre construction is completed. Next, we prove that tr(G) : L(M) by demonstrating L(G) e L@) and L(M) e fg1. First, we prove L(G) e L$,1). Bv induction, we demonstrate Claims A, B and C.
Claim A. S +' ),arpp in G irnplies€f a Zp(X, X) 1* o(Z,arp)u in IvI, w h e r cX , Z € N , a , g , ) , p , € V * , r € l / 2 u , n /u ? u i e ) , a € T * , o € . f * . Basis L e t i : 0 . T h e n , 9 + 0 , S i n G . B y V I I , Z p ( X , X ) * € f e R f o r e v e r yX e l / , so e/ I Zp(S, S) 1o Zp(,g,S) in M.
Induction Hypothesis. Assume that Claim A holds for every i 1 n, where n is a positive integer.
Induction Step. Consider any derivation of the form 5 =1n*1 \aa/p and expressthis derivationas,S =+' ),anBp,+ ),ayBp,,wlierer,U € l/2u.n/u?u{u}, a, C.,\, 1,t€" V" .
By the induction hypothesis, f i* o(Y,arp)u t o(Y,ay7)r,., in &1, where o € 1". The next three casescover all possibilities how G can make the derivaLion Aarpp. + ),ayljp,. a) Let A -"+a e P, r, : A, U : a, w h e r ea € T u { r i , A e I Y .
Then, )aApp, + ),aaBpr,lA* o] in G.
By III, Z (X, aaB) --. Z \X, aAp) e R, s o 5 Z ( X , a r B ) a ) 6 2 ( X , a y B ) w r n l u [ , Z e l , d e f . . b ) L e LA - . B C e P , r : A , y : B C , wherc A, B, C e .V.
Then, ),a-4Bp + ),aBC0plA -. BC) in G.
By Va, Z \X, aBC B) -- Z (X, aAp) e R, s o 6 2 ( X , , a x B ) w1 6 2 \ X , a A P ) u i n M , Z e f , d e f * .
On Vertical Grammatical Restrictionsthat Producean Infinite LanguageHierarchy
! Claim B. LeL r,y e T" are two adjacent terminal segmentsof any sentence 'u,e L(G), lrl, lgl < k. If there existsa derivationof the form astslsps)* e r r r A t B t A t h + e t r t . C t D t A t / r l p t ] 1 * a 2 r 2 A z B z A z ] z+ a2r2C2Dzaz1zlpz)=+* ... =+* axriAiBiU,0, + air2CxDiat,1tlpr)+" aryp in G, where every Pi : ArB, - CrD, € Pcs rewrites Ai and Bi o\ boundary i n a c o n t e x tw a y ( A i , B i , C i , D i € N , a , 0 , , a * , C ^ € V * f o r j - 1 , 2 , . . . , , i , m , : 0 , 1 , . . . , i ) , t h e r r
Z p u ( X , r ) A a l " Z p ( X , r i C ) y a | ( p ) Z p \ X , r ; A ; ) A a a " . . . . . . F * ( p r ) . . ( p t ) Z r ( X , r 2 C 2 ) y a t ( p n ). . . ( p r )( p r ) Z p \ X , r 2 A 2 ) a a l * ( p , ) . . . h s ) ( p r ) Z p ( X , r r C t ) u , | @ n ) .. . ( p r ) ( p r ) ( p t ) Z p ( X , : D 1 A 1 ) ' yra* ( p o ). . . ( p . ) ( p r ) ( p t ) z p \ X , r o ) v u and Bas'is Let i_ 0. Then aoroUo1o =9* anAP in G. In this case, there is no rewriting in a context way between the investigated columns, so productions are applied only insidethesecolumns.Thus, rn NI, Zp(X,r)Au l* Zp(X,rs)ya and Zp(Y,y)a ?- Zp(Y,Ao)a, where only reductions inside the columns are simulated(seeClaim A).
Induction Hypothesis Assume that Ciaim B holds for every i 4 t, where f is a positive integer.
Inrht,cti,onStep By the induction hypothesis,
Z p u ( X , r ) a u l * Z p ( X , r t + t Ct + t ) y u | ( p t * r ) Zp \ X , ,r t + r A t + r ) y a l * ( p t o t )Z p ( X , r 1 C ) y w F ( p r * r ) ( p t )Z p \ X , r l A l l y a ? * . . . . . . F * ( p t + t ) ( p r ) . . ( p s )Z p ( X , r 2 C 2 ) y u I (p'+r) (p') . . . be) (pr)z p \x, r2A2)aa t* ( p t + t ) ( p r ). . . ( p s )( p z )z p ( x , r r c 1 ) t 1 u I (pr*t)(p,) . . . (pr)(pz)(pt)z p (x,, rrAt)vw r* (p,+r) (p') . . . (ps)(pr)(pt) z p (x, ro)au t 7 6 R. Bidlo, P. Blatny and A. Meduna z p (pr)(pr) . . . (pt-r) (p') (p'*t) (Y,y)u r. z p ( p r ) ( p r ) . . . ( p r - t ) ( p r ) ( p t * t ) ( Y , D t + , , a t + t ) aI z p ( p t ) ( p r ) . . . ( p t - r ) ( p , ) ( Y ,B t + f l i , + r ) , F * zp(pt)(pr) . . .(p'-t)(pr)(Y, Ds)u I Zp(pr)(pr) . . .(pt-r)(y, Btat)a F* . . .r* Zp(pt)(pr)(Y, D2y2)uI Z p(pt)(Y, BzAz), F. Z p('pt)(Y,Dt,yt)a I
Z p \ Y , B r y t ) , F . Z p ( Y , y d u By IVa and IVb, for every production of the form AB -- C D e P, there are productions of the form Zp\X,aC) --) (AB -- CD)ZI\X,aA) and (y'B -' CD)\X.Dp) --r \X,BP) in fi. These productions simulate the transitions of t h e f o r m ( p t * r ) . ( p , - t ) Z p ( X , r , C , ) A a | ( p r * t ) . . . ( p , - t ) ( p , ) Z p \ X , r , A , ) y u a n d Z p ( p r ) . . . ( p , - r ) ( p " ) ( Y , D , A , ) u l Z p ( p t ) . . . ( p " - r ) ( ) ' , B " A , ) w r n I v I, w h e r e T , s : t + 1 , t , . . . , 1 . s o C l a i mB h o l d s . t r All other derivation and transition steps in G and M are investigated in Claims A and C.
Clairn C. )zp +' \'"1"' in G i m p l i e su ( Z , a z p ) , F * u ( A , Y ) u ' t n M , w h e r e l , ) ' , p , , p l€ V * , Z , r e l { 2 U N , A , Z € .N , a , w ' e T * a n d u , u € l * . F o r l r l : 1 , there are A : tr, Y e ,A/and for r : x 1 r 2 , r r , r 2 € N , t h e r e a r eA - 1 2 , Y : € . Busis Let i: 0. Then Azp,+o )zp. in G. Clearly, u(2, azB)w l0 u(2, azB)u in llvrl .
I'nduct'io'nHypothesis Assume that the implication in Claim C holds for every i I 9.,where g is a positive integer.
Inducti,onStep Considerany derivation of the form \z p. +o+t ^'a Lt' and express i t a s ) z p + s \ ' r p ' ) \ ' A p ' , w h e r er , U , z e I V 2U N , \ , 1 f , , \ ' , 1 1 , ' € V * . B y t h e i n d u c t i o n h y p o t h e s i s ,' u ( Z , a z B ) w a s , u ( A , Y ) a ' l , ( A ' , Y ' ) r ' i n I v I , 'ti,)'u)'u€l f*. Next, we examine the derivation \'rl"'+ \'Ap'in G.
Let A --- BC € P, tr : A, A : UtAz * BC, where A,B,C e l/. Then, X A p ' = + \ ' B C p ' [ A - - - ] B C I i n G . B y V b , Z z ( A , B ) - * ' Z p \ C , e ) € R , s o w Z p ( r , A t ) u t w Z p ( y r , r ) , i n M , , w h e r eu t e f * . n Observethat Claim C holds.By Claims A, B, and C, L(G) g L(M) holds. Tlre complete proof of the secondinclusion, L(M) e LG), unfortunately exceedsthe page limit of this paper, so we leave it on the reader and we only shortly outline its structure.
The proof of this inciusion is based on the form of computation of flippushdown automata, where there can be identified some main parts in the corlputation, whicir are closely linked to the corlesponding derivation sequences in the grammars restricted in the vertical way described before. Bv this it is On Vertical Grammatical Restrictionsthat Produce an Infinite LanguageHierarchy proved that these automata can simulate every derivation in the vertically restricted gralnmar from the bottom, where the parsed sentenceis read and processedcolurnn-by-colurnn.Therc is thc pushdown flip perforrned between every two consecutive columns, so the context-sensitive derivations on the column's boundaries can be efficiently simulated on the pushdown.
By this, L(AI) g LG) is proved and thtrs Thcorcm t holds. I From the previous result, somecorollariesfollow. To formalize them, consider a phrase-stntcture grammar Gi, in Kuroda normal form satisfying the vertical restrictions from Theorem 1, which generatesevery w € L(G i) by using exactly i columns.Name this grammar as ani-column gramrna7where i>I. Denote KNF1 the family of languagesgeneratedby i-column grammars.
C o r o l l a r y 2 . C F : K N F 1 C K N F 2 C . . . C K N F . " - R E
The introduced restrictions preserveall forms of derivation rules defined by the Kuroda norrnal forrn of phrase-structuregrammars. Notice that there were no restrictions on the number of derivation stepsin the particular columns introduced, but only the order of context-sensitivederivations on boundaries was restricted. As a result, rve found a new infinite language hierarchy generatedby grammars restricted in this way, witere the lorvestfamily of languagesin this hierarchy is equal to the context-free languagesand the highest family correspondsto the family of recursively enumerablelanguages.This resuit is very interesting in the forrnal language theory and extends the area of infi.nite languagehierarchiesby a new type.
This work has beensupportedby the Grant Agency of CzechRepublicarants I,{o. 201/07/0005.