Tillväxtlemma för sammanhangsfria språk

Tillväxtlemmat för kontextfria språk  är ett lemma som, i analogi med lemma med samma namn för reguljära språk, gör det relativt enkelt att bevisa att ett givet språk inte är kontextfritt .

Formulering

Om L är ett CS-språk över alfabetet V, då . Med andra ord kan vilken tillräckligt lång kedja som helst i CS-språket delas upp i fem delar så att upprepningen av den andra och fjärde delen ett godtyckligt antal gånger (kanske 0) inte leder till att man går utanför språket.

Bevis

Låt ett CS-språk (V, N, S, G) ges, och språkets grammatik reduceras (det vill säga att det inte innehåller regler av formen A → ε eller A → B).

Eftersom antalet icke-terminala symboler är ändligt, liksom längden på varje slutledningsregel, begränsas längden på kedjan, vars höjd av härledningsträdet inte överstiger |N|, också uppifrån av en viss nummer n.

Låt oss överväga en kedja . På grund av ovanstående kommer höjden på dess härledningsträd att överstiga |N|, det vill säga det kommer att finnas en väg från axiomet till en av terminalsymbolerna, vars längd kommer att vara större än antalet icke-terminala grammatikens symboler. Eftersom en icke-terminal symbol ersätts vid varje steg, kommer åtminstone en icke-terminal Q-symbol att ersättas två gånger i denna väg. Det följer av detta att det finns en kedja xQy med icke-tom x eller y som härrör från Q. Därför, i härledningsprocessen S →* α, kan härledningsprocessen Q →* xQy upprepas så många gånger som önskas eller utelämnas.

En trivial följd: i vilket oändligt CS-språk som helst finns det en oändlig delmängd av strängar vars längder bildar en ökande aritmetisk progression.

Användningsexempel

• Språket är inte ett CS-språk: det är omöjligt att välja två kedjor och ladda ner dem utan att lämna språket (du måste ladda ner tre kedjor samtidigt).
• Språket är inte heller ett CS-språk, men det kommer inte längre att vara möjligt att bevisa detta genom att "pumpa": du kan pumpa upp "zoner" av tecknen a och b, och dra nytta av att det kan finnas färre c-tecken i kedjan. Men om vi betraktar strängen som hör till språket , så kommer antingen uteslutningen av pumpade strängar att ta oss ur språket, vilket motsäger det pumpande lemmat.
• Språket är inte heller ett CF-språk, eftersom det motsäger lemmats konsekvens.

Se även

• Pumpande lemma för vanliga språk
• Kontextfri grammatik

Litteratur

• John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Introduktion till automatteori, språk och beräkningar. - M .: "Williams" , 2002. - S. 528. - ISBN 0-201-44124-1 .
• A.I. Belousov, S.B. Tkachev. Diskret matematik / ed. d.t.s. prof. V.S. Zarubina, Ph.D. prof. A.P. Krishchenko. - 4:e uppl., rev. — (matematik vid tekniskt universitet). - 2000 exemplar.  — ISBN 5-708-2886-4.