A 10. óra vázlata: Példák
Ismert a római számok halmaza, amely intuitív szintaxissal rendelkezik, hiszen pl. o
IIV-t
o
VX-et vagy
o
Olyan szintaxis utasítja el ezeket a jelsorozatokat, amely szerint o
megelőző helyzetben legföljebb egy jel lehet
o
megelőző helyzetben csak 10-hatvány lehet
o
legföljebb három egyforma jel állhat egymás mellett
Reguláris nyelvtanokkal kapcsolatosan most egy engedményt teszünk: o
o
o
IIII-t nem fogadjuk el római számnak (habár… v.ö. tarokk-kártya vagy némely óra számlapja)
Nemcsak az A x illetve az A xB formákat fogadjuk el, hanem az A p illetve az A pB formákat is, ahol p T* (Előadáson beláttuk, hogy ez az engedmény megtehető a generálási képesség kiterjesztése nélkül: azaz a lazább értelemben definiált reguláris nyelvtanok ugyanazokat a nyelveket generálják, mint a szigorúak.)
Ennek az engedménynek az alkalmazásával tekintsük most a következő nyelvtant (a római számjegyeket most kisbetűvel jelöljük, hangsúlyozva, hogy ők a terminálisok): o
G1 = ({i, v, x, l, c, d, m}, {R}, R, H), ahol H elemei:
Ri
R ii
R iii
R iv
…
R xlviii
R xlix
o
o
R iiii (eldönthetjük, hogy ezt a 4-est bevesszük-e vagy sem)
R il (ismét eldönthetjük, hogy az eltérő szintaxisú, de azonos szemantikájú [a római szám szemantikája az értéke!] jelsorozatokat bevesszük-e a nyelvbe)
Rl
…
R mmmcmxcix
A G1 nyelvtannak van egy nagyon fontos tanulsága: Minden véges nyelv reguláris. Tekintsük most a következő G2 nyelvtant: G2 = ({i, v, x, l, c, d, m}, {R, M, C, X, I}, R, H), ahol H elemei (itt bevezetünk egy összevonási lehetőséget: ha a nyelvtanban szerepel egy P Q1 és egy P Q2 szabály, akkor ezeket összevontan P Q1|Q2 alakban írjuk):
R MCXI
M mmm|mm|m|
C cm|dccc|dcc|dc|d|cd|ccc|cc|c|
X xc|lxxx|lxx|lx|l|xl|xxx|xx|x|
I ix|viii|vii|vi|iv|v|iii|ii|i|
o
Mindjárt felhívjuk a figyelmet két — generálás szempontjából — fontos különbségre:
G2 nem engedi meg a szintaktikai variánsokat (iiii, il)
L(G1) míg L(G2)
o
Van azonban még egy nagyon fontos különbség G1 és G2 között: G1 reguláris, G2 környezetfüggetlen. (Gyakorlat: Miért? Keressük meg G2 helyettesítési szabályai között azt a szabályt [segítség: egy ilyen van], amely G2-t környezetfüggetlenné teszi.)
o
Ez utóbbi kérdés a -tartalmazás kérdése: mi legyen az álláspontunk akkor, ha két nyelv csak abban tér el, hogy az egyik tartalmazza a -t, a másik nem — ettől eltekintve egyenlők? A válasz az, hogy nyelvtani szempontból tekinthetők egyenlőnek, van ugyanis egy tétel, amely szerint minden grammatika -mentessé tehető, ami alatt azt kell érteni, hogy az új (és egyébként ekvivalens) grammatikában sehol sem fordul elő helyettesítési szabály jobb oldalán, kivéve esetleg az S szabályt, azaz a — ha mégis be akarjuk venni a nyelvbe — közvetlenül a mondatszimbólumból levezethető (de csakis abból).
Kérdés, hogy a római számok halmaza (nyelve) ettől környezetfüggetlen nyelvvé vált-e. Nyilván nem. A nyelv Chomsky-osztályát ugyanis a legmagasabb indexű grammatika határozza meg, amellyel generálható. G1-gyel megmutattuk, hogy a római számok generálhatók reguláris (azaz 3-as indexű) grammatikával, vagyis a nyelv Chomskyosztálya 3-as.
Legyen az a törekvésünk, hogy a szintaxist közelítsük a szemantikához! Tekintsük ennek érdekében a
következő G3 nyelvtant: G3 = ({i, v, x, l, c, d, m}, {R, M, C, C300, X, X30, I, I3}, R, H), ahol H elemei
o
R MCXI
M mmm|mm|m|
C300 ccc|cc|c|
C C300|dC300|cd|cm
X30 xxx|xx|x|
X X30|lX30|xl|xc
I3 iii|ii|i|
I I3|vI3|iv|ix
Vegyük észre előszöris, hogy L(G2) = L(G3), tehát a két nyelvtan ekvivalens. A G3 nyelvtan viszont valamivel „beszédesebb”: a tízhatványok hármas csoportosításával többet árul el a római számok szemantikájából, mint a G2. (És nem mellesleg csak 29 szabályból áll, szemben a G2-vel, amely 35-ből.)
o
o
Házifeladat: olyan G4 grammatikát készíteni, amely a megelőző helyzeteket is hasonlóan szemantikusan kezeli.
Vizsgáljuk most a következő G5 nyelvtant (nemterminálisok kisbetűk, terminálisok nagybetűk, mondatszimbólum az S):
S xS
S yS
S zS
S
Könnyen látható, hogy L(G5) = {x, y, z}* = T*.
T* tehát reguláris nyelv.
Kérdés, mi generálja T+ nyelvet. Ha az az első ötletünk, hogy a G6
S xS
S yS
S zS
nyelvtan, akkor ez a gondolat téves. Ugyanis L(G6) = . Ehelyett tekintsük a G7
S xS
S yS
S zS
Sx
Sy
Sz
nyelvtant! Amint könnyen megfontolható: L(G7) = T+. o
o
o
Vegyük észre, hogy G7 úgy nyerhető G5-ből, hogy mentesítést végzünk, de az S szabályt (szándékosan) nem alkalmazzuk! Vizsgáljuk most azt a nyelvet, amelynek a terminális halmaza ugyancsak {x, y, z}, de a nyelvbe csak a head(p) = x tulajdonságú jelsorozatok tartoznak bele. Egyszerű megfogalmazással: azok a p-k, amelyek xszel kezdődnek. (A head függvény leválasztja a jelsorozat első elemét.) Megfontoltuk, hogy ezt a nyelvet az alábbi G8 nyelvtan generálja:
S xA
A xA
A yA
A zA
A
Végül keressünk nyelvtant a lengthx(p) = 1 tulajdonságú nyelvnek! (Ezek olyan sorozatok, amelyeken
pontosan egy x van.) A következő G9 nyelvtant találtuk erre a célra:
o
S AxA
A yA
A zA
A
Könnyen belátható, hogy L(G9) = {p | lengthx(p) = 1}. Igen ám, de G9 környezetfüggetlen nyelvtan. Kérdés, hogy vajon {p | lengthx(p) = 1} környezetfüggetlen nyelv-e.
Házifeladat: {p | lengthx(p) = 1}-nek reguláris grammatikát keresni.
