The descriptional complexity of semi-conditional grammars is studied. A proof that every recursively enumerable language is generformal languages, descriptional complexity, semi-conditio-
This paper studies the descriptional complexity of semi-conditional grammars (see [4,7-9] for more details) with respect to the number of conditional productions and nonterminals.
Semi-conditionalgrammars are modified context-freegrammars, where a permitting and a forbidding context is associatedwith eachproduction. This means that a production is applicable if its permitting context is contained in the current sentential form and its forbidding context is not. As a special caseof semiconditional grammars, we obtain simple semi-conditional grammars introduced in [3], where one of the contextsis required to be a specialsymbol 0, i.e., either a permitting or a forbidding context is associatedwith each production.
Whereas the descriptional complexity of simple semi-conditionai grammars
has been studied carefully (see[5,7, B,10]), the descriptional complexity of
semiconditional grammars has not been studied at all, and all results concerning
the descriptional complexity of semi-conditional grammars are consequencesof
results concerningthe descriptional complexity of simple semi-conditional
grammars. Specifically,in [8], u proof that every recursively enumerable language is
generatedby a (simple) semi-conditional grammar of degree (
In [2], it was shown that every recursively enumerablelanguageis generated by a grammar
G : ( { S ,A , B , C ) , 7 , P U { A B C - + s } , S ) in the Geffert nor.malform, where P contains context-free productions of the form
S -, uSa, S -. uSu, S '-+uu, w h e r eu e { A , A B } . , a e T , w h e r eu € { A , A B } - , u € { B C , C } * , w h e r eu € { A , A B } . , , u e { B C , C } - .
In addition, any terminal derivation is of the form by productionsfrom P, where wt e {A, B}-, u2 € {B,C}.,, w e ?*, and ,S=+* w1u2w
W1U2W 1" 111
G : (l/, T, P, S), by ABC -- e.
A semi,-condi,tiognraal mmar,G,is a quadruple where - ,Afis a nonterminal alphabet, - ? is a terntinal alphabet such that I/ )T :0, - S e l/ is the start sYmbol, and - P is a fi.niteset of productions of tlr.eform
( X * a , u , u ) w i t h X € l / , a € ( l / U ? ) - , a n d u , t ) e ( l / u T ) * a specialsymbol. u { 0 } , r v h e r e0 / I / u T i s A Note on the Descriptional Complexityof Semi-ConditionalGrammars It u l0 or u f 0, then the production (X - a,u,u) € P is saidto be condi,t'ional. G has degree(i, j) if for ali productions(X , etu,u) € P,u* 0 impliesl"l <i and u l 0 implies lul < j. For n € (.4/UZ)+ and y € (liU?)., r directly deriues y accordingto the production (X * a,u,u) € P, denotedby
n + a i f .r : r 1 X r 2 , U : r y a r , 2 , f o r s o m ef r r t r z € ( l f U T ) * , a n d u ,l 0 i m p l i e st h a t u e sub(r) and u + 0 implies that u / sub(r). As usual, =+ is extendedto =)', for i ) 0, 9*, and +*. The languagegeneratedby a semi-conditionalgrammar, G, is defined as g ( G ) :
{ w e T " : S = + *u } .
Let G: (l/,7,P,.9) be a semi-conditionaglrammar. If (X > e..tt",u)€ P implies that 0 e {u,u}, then G is said to be a si,mpLseemi,-condi,ti,ongarlo,n'Lmar.
This section presentsthe main result concerningthe descriptionai complexity of semi-conditic.rnaglrammars.
Theorem 1. Euery recursiuelAenumerable language i,s generated by a
semiconditional grammar of degree(
Proof i,dea.
The main idea of the proof is to simulate a terminal derivation of a grammar, G, in the Geffert normal form.
To do this, we first appiy all context-free productions as applied in the G's derivation, and then we simulate the production ABC --+ E so that we mark with ' only one occurrenceof A, one of B, and one of C and check that these marked symbols form a substring A'B'C' of the current sentential form. If so, the marked symbols can be removed, which completes the simulation of the production ABC --+e in G; otherwise, the derivation must be blocked.
The formal proof follows.
Proof. Let L be a recursively enumerablelanguage.There is a grammar
G : ( { S , A , B , C } , T , P U { A B C - + s i , ^ 9 ) in thc Geffcrt normal form such that L: 9(G). Construct the grammar where and P" contains foiiowing sevenconditional productions:
G' : ({^9A,, B, C,A' , B' , C', $},7, P' U P" ,,S),
P ' : { ( X * a , 0 , 0 ) : X - - - a e P } , 1 . ( A * $ , 4 ' , 0$, ) , 2 . ( B - B ' , A ' , B ' ) , 3 . ( C - C ' $ ,A ' B ' , C ' ) , 4 . ( B ' - e ,B ' C ' , 0 ) , , 5 . ( C ' - e ,A ' C ', 0 ) , 6 . ( A ' - e , A ' $ , 0 ) , 7. ( $ - e , 0 ,A ' ) .
To prove thar I (G) e g(G'), considera derivation
,S=+* wABCw'y ) 111111ty in G by productions from P with only one application of the production ABC -e, w h e r ew , w ' e { A , B , C } * a n d u € .T * . T h e n ,
S + * w A B C w ' u in G' by productions from P'. iVloreovert,ry productions r, 2, z, 4, b, 6, 7, 7, we bC-'p"r.
uABCw'u + w$A'BCw'u + w$A'B'Cw'u + w$A'B'C'$w'u + w$A'C'$w'u + w$A'$w'u =+tl$$tr'u + w $ w ' u + lt;lt)'U.
To prove that 9(G) )_ -?(G'), consider a terminal derivation. Let X € {A,B,C} be in a sententialform of this d.erivation.To eliminate X, there are followirig three possibilities: 1. If X - A, then there must be C and A (bV productions 6 and 3) in the derivation; 2. If X - B, then there must be C and A (by productions 4 and 3) in the derivation; 3. If X - C, then there must be A and B (bV productions 5 and 3) in the derivation.
In all aboveca^sest h,ere areA, B, and C in the derivation. By productions 1,2,
3, and 7, there cannot be more than oneA', B', and C, in any sentential form of
this terminal derivation. Nloreover,by productions 3 and ,1,A' B'C' is a substring
of a sentential form of tltis terminal derivation, and.there is no terminal syrnbol
between any fwo nonterminals; otherrvise,there will be a situation in which (zrt
A Noteon theDescriptionaClomplexitoyf Semi-ConditionaGlrammars
Ieast) one of productions 3 and 4 will not be applicable. Thus, any first part of
a terminal derivation in G' is of the fornr
,S+* ulABCw2w +3 wt$A'B'C'$w2w
(
I wt,g.AC' '$wzw .
Besidesa possible application of production 2, oniy production 5 is applicable. Thus, where tr', € {A,B,B'}*,.L € {8, B',,C}*. Besidesa possibleapplicationof production 2, only production 6 is applicable.Thus, w h e r ew ' i e { A , B , B ' } " , w U cable.i.e..
€ { B , B ' , C } * . F i n a l l y ,o n l y p r o d u c t i o n7 i s a p p l i Thus, by productions I, 2, 3, or 1, 3, if production 2 has already been applied, we get ++ r\9A'$w'rw ++ u'1$$w'Jw +2 w'lw'/w .
*" "tt'utD.
Here'
uutu €. {ur'A' B' c'$u2w : u1 e. {A, B}* , uz € {B , c}- } o r u u : € .
Thus, the substring ABC and only this substring was eliminated during the
previous derivation. By induction (see(