Zadacha "S-termy"
S-term - jeto posledovatel'nost' simvolov S i skobok, opredeljaemaja
rekursivno sledujuschim obrazom:
- simvol S est' S-term;
- esli M i N - S-termy, to vyrazhenie (MN) est' takzhe S-term.
Primer S-terma: ((((SS)(SS))S)(SS)). Pravye skobki ne nesut informacii i
mogut opuskat'sja. V jetom sluchae vysheprivedennyj S-term vygljadit tak:
((((SS)(SS))S)(SS.
Zadanie 1. Napishite proceduru "gensterm" dlja porozhdenija S-termov. Ona dolzhna dlja
zadannogo n zapolnjat' n tekstovyh fajlov (n = dlina = chislo simvolov 'S'),
kazhdyj iz kotoryh soderzhit vse S-termy dliny n = 1,2,...,n sootvetstvenno.
Vnutri fajla S-termy razdeljajutsja simvolom ';'. V konce kazhdogo fajla dolzhen
stojat' simvol '.' (tochka).
Napishite programmu, kotoraja po zadannomu celomu n (n <= 10) vypolnjaet
opisannuju vyshe proceduru i vydaet na displej vse sgenerirovannye S-termy.
Rassmotrim vychislenie S-termov. Edinstvennoe algebraicheskoe pravilo
(S-pravilo), kotoroe mozhet byt' ispol'zovano, sostoit v sledujuschem: ljuboj
podterm S-terma, imejuschij vid (((SA)B)C), gde A, B, C - takzhe S-termy, mozhet
byt' perepisan kak ((AC)(BC)), to est' Context1(((SA)B)C)Context2 ->
Context1((AC)(BC))Context2.
Primenenie jetogo pravila k S-termu nazyvaetsja redukciej S-terma. Vozmozhny
raznye sposoby (strategii) vybora podtermov dlja primenenija S-pravila.
Posledovatel'noe primenenie S-pravila k S-termu do teh por, poka jeto
vozmozhno, nazyvaetsja normalizaciej.
Primer cepochki redukcii S-terma:
((((SS)(SS))S)(SS)) -> (((SS)((SS)((SS)S))(SS))
-> ((S(SS))(((SS)S)(SS))) -> ((S(SS))((S(SS))(S(SS)))).
Zadanie 2. Predlozhite jeffektivnuju strukturu dannyh dlja predstavlenija S-termov, oblegchajuschuju primenenie S-pravila. Napishite dve procedury: "readterm" i "printterm". Pervaja iz nih preobrazuet S-termy v Vashu strukturu dannyh iz formy, porozhdaemoj proceduroj "gensterm"; vtoraja preobrazuet S-termy iz Vashej struktury v formu, porozhdaemuju proceduroj "gensterm". Vasha programma dolzhna demonstrirovat' jeti preobrazovanija.
Zadanie 3. Napishite proceduru "reduce", vypolnjajuschuju odin shag redukcii v sootvetstvii s S-pravilom nad zadannym podtermom S-terma v Vashem predstavlenii. Programma dolzhna demonstrirovat' jeto.
Zadanie 4. Napishite proceduru "normalize", kotoraja v zadannom S-terme dolzhna posledovatel'no vybirat' podtermy i primenjat' S-pravilo do teh por, poka dal'nejshii redukcii stanut nevozmozhnymi, libo chislo shagov ne dostignet nekotorogo maksimuma, naprimer 30. Vasha programma dolzhna demonstrirovat' jeto.
Zadanie 5. Ob''edinite vse procedury v odnu programmu, kotoraja:
- zaprashivaet u pol'zovatelja dlinu n;
- porozhdaet s pomosch'ju procedury "gensterm" S-termy zadannoj dliny;
- preobrazuet vse S-termy v Vashe predstavlenie;
- normalizuet ih (esli jeto vozmozhno);
- vyvodit v kachestve rezul'tata normalizovannye S-termy;
- vyvodit posledovatel'no chislo shagov redukcii, sovershennyh nad kazhdym S-termom, libo soobschenie "not normalized", esli normalizacija trebuet bolee 30 shagov;
- vyvodit chislo nenormalizovannyh termov i obschee chislo vseh S-termov zadannoj dliny n.
