K¨ornyezetf¨uggetlen nyelvek Kieg´esz´ıt˝o anyag az Algoritmuselm´elet t´argyhoz VI. (a R´onyai–Ivanyos–Szab´o: Algoritmusok k¨onyv mell´e) Friedl Katalin BME SZIT
[email protected] 2016. febru´ar 24. A regul´ aris nyelveket v´eges automat´akkal vagy regul´aris kifejez´esekkel adtuk meg. Van tov´ abbi lehet˝os´eg is, ezek a form´ alis nyelvtanok vagy r¨oviden nyelvtanok. A form´ alis nyelvtanok nem eg´eszen olyanok, mint p´eld´aul a magyar nyelvtan. B´ ar eredetileg a term´eszetes nyelvek szab´alyainak le´ır´as´ara k´esz¨ ultek, de ink´ abb haszn´ alhat´ oak mesters´eges nyelvek, p´eld´aul programoz´asi nyelvek pontos megad´ as´ ara, mint egy besz´elt nyelv helyes mondatainak t¨ok´eletes le´ır´as´ara. A form´ alis nyelvtanok l´enyeg´eben ´at´ır´asi szab´alyokat adnak meg, amikkel egy kezd˝ o szimb´ olumb´ ol kiindulva szavakat tudunk el˝o´all´ıtani. Ezeknek itt csak egy speci´alis, tal´an a leggyakrabban haszn´alt fajt´aj´aval foglalkozunk. 1. Defin´ıci´ o. Egy k¨ ornyezetf¨ uggetlen nyelvtan (r¨ oviden CF nyelvtan) alatt egy olyan G = (V, Σ, S, P ) rendszert ´ert¨ unk, ahol • V egy v´eges, nem u ¨res halmaz, a v´altoz´ok (vagy nemtermin´alisok) halmaza, • Σ egy ´ ab´ec´e, amire V ∩ Σ = ∅, a karakterek (vagy termin´alisok) halmaza • S ∈ V a kezd˝ o v´ altoz´ o, • P egy v´eges halmaz, az u ´n. levezet´esi (vagy produkci´os, illetve ´at´ır´asi) szab´ alyok halmaza. P elemei A → α alak´ uak, ahol A ∈ V egy v´ altoz´ o, α ∈ (V ∪ Σ)∗ egy v´ altoz´ okb´ ol ´es a Σ elemeib˝ ol a ´ll´ o tetsz˝ oleges, v´eges hossz´ u sorozat. 1. P´ elda. Legyen V = {A}, Σ = {a, b}, a kezd˝ o v´ altoz´ o term´eszetesen az A, a levezet´esi szab´ alyok halmaza pedig P = {A → aAb, A → ε} 1
A nyelvtanok megad´ as´ an´al sokszor nem ´ırjuk ki az ¨osszes param´etert, csak a levezet´esi szab´ alyokat soroljuk fel. Ha m´ast nem mondunk, akkor a szab´alyokban szerepl˝ o kisbet˝ uk a Σ elemei, a nagybet˝ uk a v´altoz´ok, az els˝o szab´aly bal oldala a kezd˝ o v´ altoz´ o. Tov´ abb´ a azok a szab´alyok, melyeknek a bal oldal´an ugyanaz all, ¨ ´ osszevonhat´ oak, f¨ ugg˝ oleges vonallal elv´alasztva a k¨ ul¨onb¨oz˝o jobb oldalakat, Ebben a form´ aban az el˝ oz˝ o nyelvtan ´ıgy n´ez ki: A → aAb | ε 2. Defin´ıci´ o. Egy G = (V, Σ, S, P ) nyelvtann´ al levezet´es alatt egy olyan γ0 ⇒ γ1 ⇒ γ2 ⇒ · · · ⇒ γn v´eges hossz´ u sorozatot ´ert¨ unk (n ≥ 0), melyben γ0 = S, tov´ abb´ a γi ∈ (V ∪ Σ)∗ , ´es mindegyik γi+1 megkaphat´ o γi -b˝ ol egy levezet´esi szab´ aly alkalmaz´ as´ aval. Ez azt jelenti, hogy minden 0 ≤ i < n eset´en γi fel´ırhat´ o γi = δ1 Aδ2 alakban, ahol δ1 , δ2 ∈ (V ∪ Σ)∗ ´es A ∈ V u ´gy, hogy ´es γi+1 = δ1 αδ2 ahol A → α egy P -hez tartoz´ o levezet´esi szab´ aly. 2. P´ elda. Az el˝ oz˝ o nyelvtan eset´en egy levezet´es pl. az al´ abbi A ⇒ aAb ⇒ aaAbb ⇒ aaaAbbb ⇒ aaaεbbb Az ´ıgy levezetett sz´ o az aaabbb. K¨ onny˝ u l´ atni, hogy ebb˝ ol a nyelvtanb´ ol pontosan azok a szavak vezethet˝ ok le, amelyek an bn alak´ uak (n ≥ 0). A levezet´esek k¨ oz¨ ul azok lesznek sz´amunkra ´erdekesek, amelyekben a kezd˝o v´ altoz´ ob´ ol indulva v´eg¨ ul egy olyan sorozathoz jutunk, amiben m´ar nincsenek v´ altoz´ ok. 3. Defin´ıci´ o. A G = (V, Σ, S, P ) nyelvtan ´ altal gener´alt L(G) nyelv azokb´ ol a w ∈ Σ∗ szavakb´ ol ´ all, melyekhez valamilyen n ≥ 0 sz´ amra van olyan S ⇒ γ1 ⇒ γ2 ⇒ · · · ⇒ γn levezet´es, ahol γn = w 1. Megjegyz´ es. Vegy¨ uk ´eszre, hogy ha egy levezet´es sor´ an eljutunk egy w ∈ Σ∗ sz´ ohoz, akkor a levezet´es tov´ abb m´ ar biztos nem folytathat´ o, w nem tartalmaz v´ altoz´ ot, teh´ at ilyenkor m´ ar egyetlen szab´ aly sem alkalmazhat´ o. 3. P´ elda. Tekints¨ uk az al´ abbi nyelvtant! S → aS | bS | a | b Itt teh´ at az egyetlen v´ altoz´ o az S, az ´ ab´ec´e az {a, b}. A nyelvtanb´ ol levezethet˝ o pl. az ab sz´ o: S ⇒ aS ⇒ ab ∗
Az is l´ atszik, hogy a nyelvtan ´ altal gener´ alt nyelv {a, b} -b´ ol az ¨ osszes nem u ¨res ∗ sz´ ot tartalmazza, azaz L = {a, b} \ {ε}. Ez az´ert igaz, mert egy tetsz˝ oleges, ∗ legal´ abb 1 hossz´ u w ∈ {a, b} sz´ ohoz el˝ or˝ ol kezdve egym´ as ut´ an tudjuk gener´ alni a karaktereit: am´ıg nem az utols´ o karakterr˝ ol van sz´ o, addig az els˝ o vagy a m´ asodik szab´ allyal, az utols´ o karakter pedig a 3. vagy a 4. szab´ allyal ´ all´ıthat´ o el˝ o. 2
1. Feladat. Mely szavakb´ ol ´ all az al´ abbi nyelvtan ´ altal gener´ alt nyelv? S → aT a | bT b | a | b T → aT | bT | ε Megold´ as: Vil´ agos, hogy S-b˝ol csak olyan sz´o vezethet˝o le, ami nem u ¨res, tov´ abb´ a az els˝ o ´es az utols´ o karaktere megegyezik. Megmutatjuk, hogy a gener´ alt nyelv az ¨ osszes ilyen sz´ob´ol ´all. Ehhez vegy¨ uk ´eszre, hogy T -b˝ol minden a ´es b bet˝ ukb˝ol ´all´o sorozat el˝o´all´ıthat´o az el˝ oz˝ o p´eld´ ahoz hasonl´ oan. Az S szab´alyai lehet˝ov´e teszik, hogy a sz´o els˝o ´es utols´ o karakter´et gener´ aljuk. Ha 1-n´el hosszabb sz´ot akarunk, akkor ezek k¨oz´e a T -b˝ ol tetsz˝ oleges karaktersorozatot el˝o´all´ıthatunk. 2. Feladat. Legyen Σ = {a, b} ´es L ´ alljon azokb´ ol a szavakb´ ol, melyekben az a bet˝ uk sz´ ama megegyezik a b bet˝ uk sz´ am´ aval. Adjunk olyan G nyelvtant, amire L(G) = L. Megold´ as: Egy lehets´eges megold´as: S → aSbS | bSaS | ε Ahhoz, hogy ez val´ oban j´o nyelvtan, el˝osz¨or is vegy¨ uk ´eszre, hogy minden esetben, amikor valamelyik szab´alyt alkalmazzuk, ugyanannyi a-t gener´alunk, mint ah´ any b-t ez´ert L(G) ⊆ L. Azt kell m´eg megmutatni, hogy minden w ∈ L sz´o levezethet˝o a nyelvtanb´ol. Ezt a w hossza szerinti indukci´oval l´atjuk be. Nyilv´an ez igaz a 0 hossz´ uw=ε sz´ ora. Egy hossz´ u sz´ o nincs az L nyelvben. A kett˝o hossz´ u szavakra is k¨onny˝ u l´ atni, mert vagy az els˝ o vagy a m´asodik szab´aly egyszeri alkalmaz´asa ut´an a harmadik szab´ alyt k´etszer haszn´alva megkaphatjuk a w sz´ot. Tegy¨ uk fel, hogy L legfeljebb k hossz´ u szavair´ol m´ar tudjuk, hogy levezethet˝ ok ´es legyen |w| = k + 1. T¨obb eset lehets´eges: amennyiben w = aw0 b, akkor w0 ∈ L ´es ebben az esetben az S ⇒ aSbS kezd´es ut´an S els˝o el˝ofordul´as´ab´ol, az indukci´ os feltev´es szerint w0 levezethet˝o, miut´an a m´asodik S bet˝ ure az S → ε szab´ alyt alkalmazva megkapjuk a w sz´ot. Hasonl´ oan j´ arhatunk el, amennyiben w = bw0 a. Ha viszont w els˝ o ´es utols´o bet˝ uje megegyezik, ´es ez a bet˝ u mondjuk a, akkor vegy¨ uk w-nek egy legr¨ ovidebb kezd˝oszelet´et, amiben ugyanannyi a van mint b, legyen ez x ´es w = xy. Ekkor egyr´eszt x, y ∈ L, m´asr´eszt x sz¨ uks´eg szer˝ uen b-re v´egz˝ odik, azaz x = azb alak´ u, ahol z ∈ L. Egy ilyen w-re j´o levezet´est kapunk, ha az S ⇒ aSbS l´ep´es ut´ an az els˝o S-b˝ol az x-et, a m´asodikb´ol az y-t vezetj¨ uk le (ami az indukci´ os feltev´es miatt lehets´eges). Hasonl´ oan j´ arhatunk el akkor is, amikor w els˝o bez˝ uje b, cask ilyenkor a levezet´es az S ⇒ bSaS szab´ allyal indul. N´ezz¨ unk egy kicsit bonyolultabb nyelvtant!
3
4. P´ elda. R → XRX | S
(1-2)
S → aT b | bT a
(3-4)
T → XT X | X | ε
(5-7)
X→a|b
(8-9)
Ez is k¨ ornyezetf¨ uggetlen nyelvtan, ahol a kezd˝ o v´ altoz´ o az R. Az al´ abbi levezet´esben az al´ ah´ uzott r´esz jel¨ oli a k¨ ovetkez˝ ok´ent alkalmazott szab´ aly bal oldal´ at, a ny´ıl feletti sz´ am a szab´ aly sorsz´ am´ at. R
1
1
2
8
9
⇒ XRX ⇒ XXRXX ⇒ XXSXX ⇒ aXSXX ⇒ abSXX 8
8
3
5
7
⇒ abSaX ⇒ abSaa ⇒ abaT baa ⇒ abaXT Xbaa ⇒ abaXXbaa 9
9
⇒ ababXbaa ⇒ ababbbaa Teh´ at a kapott sz´ o ababbbaa ∈ L(G). A fenti levezet´es sor´ an t¨ obb v´alaszt´asunk is volt, hogy melyik v´altoz´ot melyik szab´ aly alapj´ an helyettes´ıts¨ uk. Egy levezet´es sokszor jobban ´attekinthet˝o ha a l´ep´eseket egy f´aba rendezz¨ uk. 4. Defin´ıci´ o. Legyen G egy k¨ ornyezetf¨ uggetlen nyelvtan ´es x egy sz´ o. Az x levezet´esi f´ aja G-ben egy gy¨ okeres fa, melyben • a gy¨ ok´er a kezd˝ o v´ altoz´ oval, • minden nem lev´el cs´ ucs egy-egy v´ altoz´ oval, • minden lev´el pedig Σ egy-egy elem´evel (vagy ε-nal) van c´ımk´ezve. • Ha egy A cs´ ucs gyerekei balr´ ol jobbra olvasva B1 , B2 , . . . , Bk , akkor a nyelvtannak van A → B1 B2 . . . Bk szab´ alya. (Itt Bi ∈ Σ ∪ V ∪ {ε}.) • A levelek balr´ ol jobbra olvasva ´eppen az x sz´ ot adj´ ak. A defin´ıci´ ob´ ol vil´ agos, hogy egy x ∈ L(G) sz´o tetsz˝oleges levezet´es´eb˝ol lehet levezet´esi f´ at k´esz´ıteni, ´es a levezet´esi f´ab´ol is kiolvashat´o legal´abb egy levezet´es. Fontos azonban megjegyezni, hogy m´ıg a levezet´es egy´ertelm˝ uen meghat´arozza a f´ at, visszafel´e ez nem igaz, ´altal´aban egy levezet´esi f´ab´ol ugyanannak a sz´onak t¨ obb levezet´ese is kiolvashat´o. 5. Defin´ıci´ o. Egy x ∈ L(G) sz´ o bal-levezet´ese egy olyan levezet´es, amikor minden l´ep´esben a γi elej´ehez legk¨ ozelebbi v´ altoz´ ot helyettes´ıtj¨ uk egy megfelel˝ o nyelvtani szab´ aly alapj´ an. Erre m´ ar igaz, hogy egy levezet´esi f´ab´ol egyetlen bal-levezet´es olvashat´o ki.
4
5. P´ elda. Az el˝ oz˝ o p´eld´ aban le´ırt levezet´eshez tartoz´ o levezet´esi fa. Ebb˝ ol t¨ obbf´ele levezet´es is leolvahat´ o, a bal-levezet´es szab´ alyai sorrendben: 1, 8, 1, 9, 2, 3, 5, 9, 7, 9, 8, 8. Jobb oldalt egy ugyanehhez a sz´ ohoz tartoz´ o m´ asik levezet´esi fa l´ athat´ o. R R
a
X
R
X
X
R
X
a
a
a
S
b
X
a
T
b
X
T
X
b
ε
b
a
R
X a
S b
T
a
X
T
X
X
T
X
b
ε
b
b
6. Defin´ıci´ o. Egy w ∈ Σ∗ sz´ o egy´ertelm˝ uen levezethet˝o a G nyelvtanb´ ol, ha G-ben csak egy levezet´esi f´ aja van. A G nyelvtan egy´ertelm˝ u, ha G-b˝ ol minden w ∈ L(G) sz´ o egy´ertelm˝ uen levezethet˝ o. Az L nyelv egy´ertelm˝ u, ha l´etezik egy´ertelm˝ u nyelvtana. Ezek szerint az el˝ oz˝ o p´eldabeli sz´o nem egy´ertelm˝ uen levezethet˝o, hiszen k´et k¨ ul¨ onb¨ oz˝ o levezet´esi f´ aja is van. ´Igy persze a nyelvtan sem egy´ertelm˝ u. 2. Megjegyz´ es. Az egy´ertelm˝ uen levezethet˝ os´eg fenti defin´ıci´ oja ekvivalens azzal, hogy a sz´ o bal-levezet´ese egy´ertelm˝ u. L´ assunk most egy fontos p´eld´at, az aritmetikai kifejez´esek nyelv´et. Az egyszer˝ us´eg kedv´e´ert csak ¨ osszead´ast ´es szorz´ast fogunk benne haszn´alni, de kieg´esz´ıthet˝ o tov´ abbi m˝ uveletekkel is. E → E + E | E ∗ E | (E) | a
(1)
Itt E az egyetlen v´ altoz´ o, az ´ab´ec´e elemei pedig +, ∗, a, valamint a nyit´o ´es csuk´ o z´ ar´ ojel. Ez egy nem egy´ertelm˝ u nyelvtan, hiszen p´eld´aul az a + a ∗ a kifejez´eshez k´et k¨ ul¨ onb¨ oz˝ o levezet´esi fa is tartozik,
5
E
E
E
+
E
a
E
∗
a
E
E
a
a
E
∗
E
+
E
a
a
3. Megjegyz´ es. Ha erre a k´et f´ ara nem mint levezet´esi f´ akra, hanem mint a kifejez´es ki´ert´ekel´es´enek m´ odj´ at megad´ o f´ akra gondolunk, akkor l´ atszik, hogy m´ıg az els˝ o megfelel az aritmetikai kifejez´esek szok´ asos kir´et´ekel´es´enek (el˝ obb a szorz´ ast v´egezz¨ uk el, ut´ ana az ¨ osszead´ ast) a m´ asodik ,,rossz sorrendben” v´egzi a m˝ uveleteket. 1. T´ etel. Az aritmetikai kifejez´esekre adott fenti G egyszer˝ u nyelvtan (1) nem egy´ertelm˝ u, de az ´ altala gener´ alt L(G) nyelv egy´ertelm˝ u nyelv. Bizony´ıt´ as v´ azlat: Az el˝ obb m´ar l´attuk, hogy a nyelvtan nem egy´ertelm˝ u. A nyelv egy´ertelm˝ us´eg´ehez mutatnunk kell egy G0 egy´ertelm˝ u nyelvtant, amire L(G0 ) = L(G). Legyen G0 a k¨ovetkez˝o: E →E+T |T T →T ∗F |F F → (E) | a Vil´ agos, hogy a G0 nyelvtannal levezethet˝o aritmetikai kifejez´esek levezethet˝ ok az eredeti nyelvtanb´ ol is. Azt kell megmutatni, hogy ha w ∈ L(G), akkor w ∈ L(G0 ) is teljes¨ ul, s˝ot a G0 -beli levezet´esi f´ aja egy´ertelm˝ u. Ezt a w hossza szerinti indukci´oval mutathatjuk meg. Ha |w| = 1, akkor csak w = a lehet, ´es ez egyed¨ ul az E ⇒ T ⇒ F ⇒ a l´ep´esekkel kaphat´o meg a G0 nyelvtanban. Hosszabb szavakra azt kell ´eszrevenni, hogy ha vannak z´ar´ojelen k´ıv¨ uli + jelek, akkor el˝ osz¨ or ezeket kell gener´alni (sorrendben visszafel´e) az els˝o szab´aly seg´ıts´eg´evel, ut´ ana a z´ ar´ ojelen k´ıv¨ uli ∗ jeleket, majd a z´ar´ojelekben lev˝o kifejez´eseket. 4. Megjegyz´ es. Vegy¨ uk ´eszre, hogy ebben a m´ odos´ıtott nyelvtanban ha a levezet´esi f´ at ki´ert´ekel´esi f´ anak tekintj¨ uk, akkor a m˝ uveletek sorrendje is a szok´ asos lesz.
6
