K¨ornyezetf¨uggetlen nyelvtan Egy G = (N, Σ, P, S) nyelvtan k¨ornyezetf¨ uggetlen, ha minden u. szab´ alya A → α alak´
Form´ alis nyelvek II. K¨ ornyezetf¨ uggetlen nyelvek ´ es veremautomat´ ak
P´eld´ ak: 1) Az S → aSb | ε nyelvtan, amely az {an b n | n ≥ 0} nyelvet gener´ alja.
F¨ ul¨op Zolt´ an
2) A Gar nyelvtan, melynek szab´ alyai
SZTE TTIK Informatikai In´ezet Sz´ am´ıt´ astudom´ any Alapjai Tansz´ek ´ ad t´er 2. 6720 Szeged, Arp´
◮
K → K + T | T,
◮
T → T ∗ F | F,
◮
F → (K ) | a.
L(Gar ) az a-b´ ol valamint a (, ), + ´es ∗ jelekb˝ ol k´epezhet˝ o aritmetikai kifejez´esek halmaza. Pl a ∗ (a + a) ∈ L(Gar ).
1/127
K¨ornyezetf¨uggetlen nyelvtan
2/127
Backus-Naur forma
3) Egy tov´ abbi p´elda a szab´ alyos z´ ar´ ojelez´eseket gener´ al´ o nyelvtan:
A gyakorlatban (pl programoz´ asi nyelvek megad´ asakor) a k¨ornyezetf¨ uggetlen nyelvtan egy makr´ o-szer˝ u v´ altozat´ at haszn´ alj´ ak. A neve Backus-Naur forma, r¨ oviden BNF. A jel¨ ol´es t¨om¨ orebb lesz, a nyelv gener´ al´ o kapacit´ as nem v´ altozik.
S → SS | (S) | ( ) P´eld´ aul: S ⇒ SS ⇒ (S)S ⇒ (( ))S ⇒ (( ))( )
1) A nemtermin´ alisokat sz¨ ogletes z´ ar´ ojelbe tett szavakkal adjuk meg, pl: hprogrami, hut.listai, a termin´ alisokat k¨ov´er kisbet˝ ukkel: if, while.
A k¨ornyezetf¨ uggetlen nyelvtanok k´et legfontosabb alkalmaz´ asa: - term´eszetes nyelvek feldolgoz´ asa (NLP),
2) A → helyett ::= jelet ´ırunk.
- programoz´ asi nyelvek szintaxis´ anak megad´ asa.
3) ”egy vagy t¨obb” makr´ o: α . . .
Az alkalmaz´ ast´ ol f¨ ugg˝ oen kisebb kiterjeszt´esek sz¨ uks´egesek (”majdnem k¨ornyezetf¨ uggetlen” nyelvtan).
pl hintegeri ::= hdigiti . . . hdigiti ::= 0|1|2|3|4|5|6|7|8|9
R¨ovid´ıt´es: cf nyelv(tan) := k¨ornyezetf¨ uggetlen nyelv(tan)
A mi jel¨ ol´es¨ unkkel: α . . . helyett A-t ´ırunk ´es felvessz¨ uk az A → Aα|α szab´ alyokat. 3/127
4/127
Backus-Naur forma
Backus-Naur forma
4) ”egy vagy egy sem” (opcion´ alis) makr´ o: [α]
Ford´ıtsuk le a sztenderd jel¨ ol´esre az L ::= S [{; S} . . .] defin´ıci´ot.
pl hifuti ::= if hrelacioi then huti [elsehuti]
a) L → S[A . . .] A →; S
A mi jel¨ ol´es¨ unkkel: [α] helyett A-t ´ırunk ´es felvessz¨ uk az A → α|ε szab´ alyokat. b) 5) ”t¨obb szimb´ olum egy egys´eg” makr´ o: {α}
L → SB B → A . . . |ε A →; S
pl hut.listai ::= huti [{; huti} . . .] A mi jel¨ ol´es¨ unkkel: {α} helyett A-t ´ırunk ´es felvessz¨ uk az A → α szab´ alyt.
c) L → SB B → C |ε C → AC |A A →; S 5/127
Korl´atoz´as n´elk¨uli, bal- ´es jobb oldali deriv´aci´ok
6/127
Korl´atoz´as n´elk¨uli, bal- ´es jobb oldali deriv´aci´ok P´eld´ ak.
Korl´ atoz´ as n´elk¨ uli deriv´ aci´ o (levezet´es): α0 ⇒ α1 ⇒ . . . ⇒ αn
Korl´ atoz´as n´elk¨ uli, bal oldali ´es jobb oldali levezet´esek az aritmetikai kifejez´eseket gener´ al´ o Gar nyelvtanban. (Az al´ ah´ uzott nemtermin´ alist helyettes´ıtj¨ uk.)
Bal oldali deriv´ aci´ o (αi legbaloldalibb nemtermin´ alis´ at helyettes´ıtj¨ uk): α0 ⇒l α1 ⇒l . . . ⇒l αn Jobb oldali deriv´ aci´ o (αi legjobboldalibb nemtermin´ alis´ at helyettes´ıtj¨ uk): α0 ⇒r α1 ⇒r . . . ⇒r αn
7/127
K
⇒
T
⇒
T ∗F
⇒
F ∗F
⇒
F ∗ (K )
K
⇒l
T
⇒l
T ∗F
⇒l
F ∗F
⇒l
a∗F
K
⇒r
T
⇒r
T ∗F
⇒r
T ∗ (K )
⇒r
T ∗ (K + T )
8/127
Korl´atoz´as n´elk¨uli, bal- ´es jobb oldali deriv´aci´ok
Korl´atoz´as n´elk¨uli, bal- ´es jobb oldali deriv´aci´ok Lemma. Minden X ∈ (N ∪ Σ) ´es w ∈ Σ∗ eset´en:
A k¨ ul¨onb¨oz˝ o levezet´esi m´ odok kapcsolata:
X ⇒∗ w
Ha X ⇒∗l α vagy X ⇒∗r α, akkor X ⇒∗ α is fenn´ all. Ford´ıtva nem igaz, p´eld´ aul Gar -ban
⇔
X ⇒∗l w
X ⇒∗r w .
⇔
Bizony´ıt´ as. Csak a baloldali levezet´esre bizony´ıtjuk (szimmetria).
K ⇒ K + T ⇒ K + T + T ⇒ K + F + T,
(a) Ha X ⇒∗l w , akkor X ⇒∗ w .
de sem K ⇒∗l K + F + T sem K ⇒∗r K + F + T nem teljes¨ ul.
(b) Tfh X ⇒∗ w , vagyis X ⇒n w valamely n ≥ 0-ra. n szerinti indukci´ oval megmutatjuk, hogy X ⇒nl w .
Ellenben, ha α termin´ alis sz´ o (α ∈ Σ∗ ), akkor az ´ all´ıt´ as m´ ar megford´ıthat´o, vagyis igaz lesz, hogy bal oldali (jobb oldali) levezet´esekkel ugyanazok a termin´ alis szavak kaphat´ ok meg mint korl´ atoz´ as n´elk¨ uli levezet´esekkel. L´ asd a k¨ovetkez˝ o di´ an.
(i) n = 0: X = w , teh´ at X ⇒0l w .
9/127
Korl´atoz´as n´elk¨uli, bal- ´es jobb oldali deriv´aci´ok
10/127
Deriv´aci´os f´ak, kapcsolatuk a deriv´aci´okkal
(ii) n ⇒ n + 1: Tfh X ⇒n+1 w , vagyis:
t1 =
X ⇒ X1 . . . Xk ⇒n w1 w2 . . . wk = w .
K
T 1) Egyr´eszt, X → X1 . . . Xk ∈ P. 2) M´ asr´eszt, minden 1 ≤ i ≤ k-ra teljes¨ ul Xi ⇒ni wi , ni ≤ n. Teh´ at, az I. F. szerint, minden 1 ≤ i ≤ k-ra Xi ⇒nl i wi is fenn´ all. A kett˝ ot ¨ osszerakva kapjuk, hogy X
⇒l ⇒nl 1 ⇒nl 2 ... ⇒nl k
T
X1 X2 . . . Xk w1 X2 . . . Xk w1 w2 . . . Xk
F
∗
t2 =
F
(
K
)
K
+
T
F
(
K
)
T
F
F
a
a
w1 w2 . . . wk = w , vagyis X ⇒∗l w .
Er˝ osen kihaszn´ aljuk, hogy w1 , . . . , wk ∈ Σ∗ . K¨ ul¨onben a fenti levezet´es nem bal oldali levezet´es lenne!
deriv´aci´os f´ak: K ⇒∗ F ∗ (K ), F ⇒∗ (a + a) 11/127
12/127
Deriv´aci´os f´ak, kapcsolatuk a deriv´aci´okkal
Deriv´aci´os f´ak, kapcsolatuk a deriv´aci´okkal
Az X ∈ (N ∪ Σ) gy¨ oker˝ u deriv´ aci´ os f´ ak halmaza a legsz˝ ukebb olyan DX halmaz, amelyre
X
X
(i) Az a fa, amelynek egyetlen sz¨ ogpontja (vagyis csak gy¨ okere) az X , eleme DX -nek.
X
X1
ε
Xn
...
(ii) Ha X → ε ∈ P, akkor az a fa, amelynek gy¨ okere X , a gy¨ oker´enek egyetlen lesz´ armazottja a ε, eleme DX -nek. t1
(iii) Ha X → X1 . . . Xn ∈ P, tov´ abb´ a t1 ∈ DX1 , . . . , tn ∈ DXn , akkor az a fa, amelynek gy¨ okere X , a gy¨ ok´erb˝ol n ´el indul rendre a t1 , . . . , tn f´ ak gy¨ oker´ehez, eleme DX -nek. X [ε]
X
tn
X [t1 , . . . , tn ]
Megjegyz´es: ha X ∈ Σ, akkor az (ii) ´es (iii) pontok nem eredm´enyeznek tov´ abbi f´ akat, teh´ at ekkor DX = {X }.
14/127
13/127
Deriv´aci´os f´ak, kapcsolatuk a deriv´aci´okkal
Deriv´aci´os f´ak, kapcsolatuk a deriv´aci´okkal
Legyen t egy X gy¨ oker˝ u deriv´ aci´ os fa. Akkor t magass´ ag´ at h(t)-vel, a hat´ ar´ at pedig fr (t)-vel jel¨ olj¨ uk ´es az al´ abbi m´ odon defini´ aljuk:
t1 =
(i) Ha t az egyetlen X sz¨ ogpontb´ ol ´ all´o fa, akkor h(t) = 0 ´es fr (t) = X .
K
T
(ii) Ha t gy¨ okere X , aminek egyetlen lesz´ armazottja ε, akkor h(t) = 1 ´es fr (t) = ε.
T
(iii) Ha t gy¨ okere X , amib˝ ol n ´el vezet rendre a t1 , . . . , tn k¨ozvetlen r´eszf´ ak gy¨ oker´ehez, akkor h(t) = 1 + max{h(ti ) | 1 ≤ i ≤ n} ´es fr (t) = fr (t1 ) . . . fr (tn ).
F
∗ (
t2 =
F
(
K
)
K
+
T
F
K
)
T
F
F
a
a
Inform´ alisan: h(t) a t-ben l´ev˝ o olyan utak hossz´ anak maximuma, amelyek t gy¨ oker´et˝ol annak valamely level´ehez vezetnek. Tov´ abb´ a, fr (t) azon (N ∪ Σ)∗ -beli sz´ o, amelyet t leveleinek balr´ol jobbra (vagy: preorder bej´ ar´ assal) t¨ort´en˝ o leolvas´ as´ aval kapunk.
15/127
fr (t1) = F ∗ (K )
fr (t2) = (a + a)
h(t1) = 3
h(t2) = 5 16/127
Deriv´aci´os f´ak, kapcsolatuk a deriv´aci´okkal
Deriv´aci´os f´ak, kapcsolatuk a deriv´aci´okkal
A deriv´ aci´ os f´ ak ´es a deriv´ aci´ ok k¨oz¨ ott a k¨ovetkez˝ o kapcsolat ´ all fenn:
I. F: Minden 1 ≤ i ≤ k-ra van olyan ti ∈ DXi , hogy fr (ti ) = αi . Legyen t az a fa, melynek gy¨ okere X , amib˝ ol n ´el vezet rendre a t1 , . . . , tk k¨ozvetlen r´eszf´ ak gy¨ oker´ehez. Ekkor t ∈ DX , tov´ abb´ a
T´ etel Tetsz˝oleges X ∈ (N ∪ Σ) ´es α ∈ (N ∪ Σ)∗ eset´en X ⇒∗ α akkor ´es csak akkor, ha van olyan t ∈ DX deriv´ aci´ os fa amelyre fr (t) = α. Bizony´ıt´ as. (a) Tfh X ⇒∗ α, vagyis X ⇒n α valamilyen n ≥ 0-ra. (i) n = 0: X = α. A t = X fa megfelel˝o lesz, mert erre t ∈ DX ´es fr (t) = X (= α). (ii) n ⇒ n + 1: X ⇒n+1 α vagyis
fr (t) = fr (t1 ) . . . fr (tk ) = α1 . . . αk = α.
(b) Tfh az X gy¨ oker˝ u t deriv´ aci´ os f´ ara teljes¨ ul, hogy fr (t) = α. t magass´ aga szerinti indukci´ o.
X ⇒ X1 . . . Xk ⇒n α1 . . . αk = α.
(i) h(t) = 0: Akkor t = X , teh´ at fr (t) = α = X . ∗ K¨ovetkez´esk´eppen X ⇒ α(= X ).
1) X → X1 . . . Xk ∈ P 2) Minden 1 ≤ i ≤ k eset´en Xi ⇒ni αi , ahol ni ≤ n. (Mellesleg: n = n1 + . . . + nk .) 17/127
Deriv´aci´os f´ak, kapcsolatuk a deriv´aci´okkal
18/127
Deriv´aci´os f´ak, kapcsolatuk a deriv´aci´okkal Legyen G = (N, Σ, P, S) egy k¨ornyezetf¨ uggetlen nyelvtan. Az el˝ oz˝ o t´etelb˝ ol azonnal kapjuk:
(ii) h(t) = n + 1: Ekkor t egy olyan fa, melynek gy¨ okere X , amib˝ ol k ≥ 1 ´el vezet rendre a t1 , . . . , tk k¨ozvetlen r´eszf´ ak gy¨ oker´ehez, ahol t1 ∈ DX1 , . . . , tk ∈ DXk .
K¨ ovetkezm´ eny. Tetsz˝oleges w ∈ Σ∗ eset´en S ⇒∗ w akkor ´es csak akkor, ha van olyan S gy¨ oker˝ u deriv´ aci´ os fa amelynek hat´ ara w .
1) X → X1 . . . Xk ∈ P 2) Legyen minden 1 ≤ i ≤ k-re αi = fr (ti ).
Ebb˝ol ´es a termin´ alis sz´ oban v´egz˝ od˝ o k¨ ul¨onb¨oz˝ o levezet´esi m´ odok ekvivalenci´ aj´ ab´ ol pedig:
I. F.: Minden 1 ≤ i ≤ k-ra Xi ⇒∗ αi . K¨ ovetkezm´ eny. Tetsz˝oleges w ∈ Σ∗ eset´en a k¨ovetkez˝ o´ all´ıt´ asok ekvivalensek:
Akkor X ⇒ X1 . . . Xk ⇒∗ α1 . . . αk = α.
19/127
◮
w ∈ L(G ),
◮
S ⇒∗ w ,
◮
S ⇒∗l w ,
◮
van olyan S gy¨ oker˝ u deriv´ aci´ os fa amelynek hat´ ara w . 20/127
Deriv´aci´os f´ak, kapcsolatuk a deriv´aci´okkal
Deriv´aci´os f´ak, kapcsolatuk a deriv´aci´okkal Defin´ıci´ o. Tetsz˝oleges x ∈ L(G ) eset´en x deriv´ aci´ os f´ aj´ anak oker˝ u deriv´ aci´ os f´ at, melynek hat´ ara x. nevez¨ unk egy olyan S gy¨
M´ as sz´ oval, a G = (N, Σ, P, S) cf nyelvtan ´ altal gener´ alt nyelv a most bevezetett fogalmak seg´ıts´eg´evel a k¨ovetkez˝ ok´eppen ´ırhat´ o fel. L(G )
=
Egy x ∈ L(G ) sz´ onak ´ altal´ aban nem csak egy deriv´ aci´ os f´ aja van. Tekints¨ uk pl a szab´ alyos z´ ar´ ojelez´eseket gener´ al´ o
{w ∈ Σ∗ | S ⇒∗ w }, Σ∗
|S
⇒∗l
S → SS | (S) | ( )
=
{w ∈
w },
=
{fr (t) | t ∈ DS , fr (t) ∈ Σ∗ }.
nyelvtant ´es az al´ abbi bal oldali deriv´ aci´ okat: S ⇒l SS ⇒l ( )S ⇒l ( )SS ⇒l ( )( )S ⇒l ( )( )( ) S ⇒l SS ⇒l SSS ⇒l ( )SS ⇒l ( )( )S ⇒l ( )( )( )
21/127
Deriv´aci´os f´ak, kapcsolatuk a deriv´aci´okkal
22/127
Deriv´aci´os f´ak, kapcsolatuk a deriv´aci´okkal
Ha megkonstru´ aljuk ezen deriv´ aci´ okhoz tartoz´o deriv´ aci´ os f´ akat, akkor a ( )( )( ) sz´ o k´et k¨ ul¨onb¨oz˝ o deriv´aci´ os f´ aj´ at kapjuk.
A deriv´ aci´ os f´ ak ´es a bal oldali levezet´esek kapcsolata: Vegy¨ unk egy x ∈ L(G ) sz´ ot.
S
S S
S ( )
S
S S
( ) ( )
S
aci´ os f´ aja egy´ertelm˝ uen meghat´ arozza az x Az x sz´o minden deriv´ egy bal oldali levezet´es´et. Ha k´et deriv´ aci´ os fa k¨ ul¨onb¨oz˝ o, akkor a bal oldali levezet´esek is k¨ ul¨onb¨oz˝ oek lesznek.
S S
Ford´ıtva, x minden bal oldali levezet´ese egy´ertelm˝ uen meghat´ arozza az x egy deriv´ aci´ os f´ aj´ at. K¨ ul¨onb¨oz˝ o bal oldali levezet´esek k¨ ul¨onb¨oz˝ o deriv´ aci´ os f´ akat eredm´enyeznek.
( )
( ) ( )
Teh´ at x deriv´ aci´ os f´ ai ´es bal oldali levezet´esei k¨oz¨ ott bijekci´ o´ all fenn!
23/127
24/127
Egy´ertelm˝u nyelvtanok ´es nyelvek
Egy´ertelm˝u nyelvtanok ´es nyelvek
Defin´ıci´ o. Egy G nyelvtan egy´ertelm˝ u, ha minden x ∈ L(G ) sz´ onak csak egy deriv´ aci´ os f´ aja van.
P´elda. A szab´ alyos z´ ar´ ojelez´eseket gener´ al´ o S → SS | (S) | ( )
A felt´etel ekvivalens azzal, hogy minden x ∈ L(G ) sz´ onak csak egy bal oldali levezet´ese van.
nyelvtan nem egy´ertelm˝ u. Mint l´ attuk, p´eld´ aul a ( )( )( ) sz´ onak k´et bal oldali levezet´ese van:
A term´eszetes nyelvek nem egy´ertelm˝ uek. Pl “L´ attam Ferit a t´ avcs˝ ovel.”
S ⇒l SS ⇒l ( )S ⇒l ( )SS ⇒l ( )( )S ⇒l ( )( )( )
Programoz´ asi nyelveknek egy´ertelm˝ ueknek kell lenni¨ uk. K¨ ul¨onben egy programnak t¨obb deriv´ aci´ os f´ aja van, amib˝ ol probl´em´ ak ad´ odnak.
S ⇒l SS ⇒l SSS ⇒l ( )SS ⇒l ( )( )S ⇒l ( )( )( )
26/127
25/127
Egy´ertelm˝u nyelvtanok ´es nyelvek
Egy´ertelm˝u nyelvtanok ´es nyelvek
P´elda. Tekints¨ uk a k¨ovetkez˝ o, Gar′ nyelvtant: ◮
K → K + K,
◮
K → K ∗ K,
◮
K → (K ), K → a.
Egy negat´ıv eredm´eny: T´ etel. Nem l´etezik olyan algoritmus, amely tetsz˝ oleges cf nyelvtanr´ol eld¨onti, hogy egy´ertelm˝ u-e. M´ as sz´ oval, nem tudunk olyan programot ´ırni, melynek inputja egy cf nyelvtan, outputja pedig igen vagy nem, att´ ol f¨ ugg˝ oen, hogy az input nyelvtan egy´ertelm˝ u vagy nem.
Ez a nyelvtan is a m´ ar ismert aritmetikai kifejez´eseket gener´ alja. Nem egy´ertelm˝ u, mert p´eld´ aul az a + a + a sz´ onak k´et bal oldali levezet´ese is van: K
⇒l
K +K
⇒l
a+K
⇒l ⇒2l
a+K +K a+a+a
K
⇒l
K +K
⇒l
K +K +K
⇒l ⇒2l
a+K +K a+a+a
Lesznek tov´ abbi rossz h´ırek is...
27/127
28/127
Egy´ertelm˝u nyelvtanok ´es nyelvek
Egy´ertelm˝u nyelvtanok ´es nyelvek
Mindk´et, eddig megismert, nem egy´ertelm˝ u nyelvtanhoz adhat´ o vele ekvivalens (ugyanazon nyelvet gener´ al´ o) egy´ertelm˝ u nyelvtan. A szab´ alyos z´ ar´ ojelez´esekhez a k¨ovetkez˝ o: B R
→ →
Defin´ıci´ o. Egy L k¨ornyezetf¨ uggetlen nyelv egy´ertelm˝ u, ha van olyan egy´ertelm˝ u k¨ornyezetf¨ uggetlen G nyelvtan, melyre L = L(G ). P´eld´ aul az a, +, ∗, (, ) szimb´ olumokb´ ol k´epezhet˝ o aritmetikai kifejez´esekb˝ ol ´ all´o nyelv egy´ertelm˝ u, mert a Gar nyelvtan egy´ertelm˝ u. A szab´ alyos z´ ar´ ojelez´esek halmaza is egy´ertelm˝ u.
(RB | ε ) | (RR
az aritmetikai kifejez´esekhez pedig a m´ar ismert Gar nyelvtan.
Az el˝ obbi k´erd´es ´ atfogalmaz´ asa: van-e nem egy´ertelm˝ u k¨ornyezetf¨ uggetlen nyelv?
K´erd´es, hogy ez igaz-e ´ altal´ aban is: megadhat´ o-e minden nem egy´ertelm˝ u nyelvtanhoz vele ekvivalens egy´ertelm˝ u nyelvtan. L´ atni fogjuk, hogy nem: van olyan k¨ornyezetf¨ uggetlen nyelv, melyhez nem adhat´ o meg ˝ ot gener´ al´ o egy´ertelm˝ u nyelvtan.
29/127
Egy´ertelm˝u nyelvtanok ´es nyelvek
30/127
Egy´ertelm˝u nyelvtanok ´es nyelvek L = {ai b j c k | i = j vagy j = k}. Tekints¨ uk az
T´ etel. L´etezik nem egy´ertelm˝ u k¨ornyezetf¨ uggetlen nyelv. P´eld´ aul, az L = {ai b j c k | i = j vagy j = k}
S A B C D
nyelv nem egy´ertelm˝ u. Pr´ ob´ aljuk meg´erteni, mi´ert.
→ → → → →
AB | CD aAb | ab cB | c aC | a bDc | bc
nyelvtant, ami L-et gener´ alja. A biztos´ıtja, hogy ”a-k sz´ ama” = ”b-k sz´ ama”. Ehhez B valamennyi c bet˝ ut hozz´ atesz. Hasonl´ oan, D biztos´ıtja, hogy ”b-k sz´ ama” = ”c-k sz´ ama”. Ehhez C valamennyi a bet˝ ut hozz´ atesz. A nyelvtan teh´ at az {ai b j c k | i = j vagy j = k} nyelvet gener´ alja. Az an b n c n alak´ u szavak viszont “dupl´ an j¨onnek l´etre”.
31/127
32/127
Egy´ertelm˝u nyelvtanok ´es nyelvek
L´ancszab´aly mentes´ıt´es Defin´ıci´ o. Egy nyelvtanban az A → B alak´ u szab´ alyokat l´ ancszab´alyoknak nevezz¨ uk.
Az an b n c n alak´ u szavak viszont “dupl´ an j¨onnek l´etre”. P´eld´ aul S ⇒l AB ⇒l abB ⇒l abc ´es S ⇒l CD ⇒l aD ⇒l abc
T´ etel. Minden G = (N, Σ, P, S), k¨ornyezetf¨ uggetlen nyelvtanhoz ′ ′ ancszab´ alymentes van vele ekvivalens G = (N, Σ, P , S), l´ k¨ornyezetf¨ uggetlen nyelvtan. Ha G 3-t´ıpus´ u, akkor G ′ is.
Teh´ at nek¨ unk sem siker¨ ult egy´ertelm˝ u nyelvtant megadni ; Ez persze nem bizony´ıt´ as.
Bizony´ıt´ as. Legyen G = (N, Σ, P, S) egy k¨ornyezetf¨ uggetlen nyelvtan. a) Minden A ∈ N-re sz´ amoljuk ki az
Bizony´ıt´ as. L´ asd: J. E. Hopcroft, J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison.Wesley, 1979, 4.7. fejezet (2nd. ed. 2001, 3rd. ed. 2006). Megadnak egy (m´ asik) cf nyelvet ´es megmutatj´ ak, hogy v´egtelen sok olyan sz´ o van, melynek legal´ abb k´et k¨ ul¨onb¨oz˝ o deriv´ aci´ os f´ aja van.
NA = {B ∈ N | A ⇒∗ B l´ ancszab´ alyok alkalmaz´ as´ aval } halmazt.
33/127
L´ancszab´aly mentes´ıt´es
34/127
L´ancszab´aly mentes´ıt´es
b) Konstru´ aljuk meg G ′ = (N, Σ, P ′ , S)-t:
P´elda l´ ancszab´ alymentes´ıt´esre.
P ′ = ∅; Minden A ∈ N-re, minden B ∈ NA -ra, /∗NA = {B ∈ N | A ⇒∗ B}∗/ minden B → α ∈ P szab´ aly eset´en: Ha B → α nem l´ ancszab´ aly akkor vegy¨ uk fel az A → α szab´ alyt P ′ -be;
G : S → A | ab, A → B | bA, B → bB | C | a, C → bb NS = {S, A, B, C }, NA = {A, B, C }, NB = {B, C } ´es NC = {C }. G ′:
Ekkor L(G ) = L(G ′ ) lesz. Ha G 3-t´ıpus´ u, akkor G ′ is.
35/127
◮
S → ab | bA | bB | a | bb
◮
A → bA | bB | a | bb
◮
B → bB | bb | a
◮
C → bb
L(G ) = L(G ′ ).
36/127
Cf nyelvtanok ε-mentes´ıt´ese
Cf nyelvtanok ε-mentes´ıt´ese Bizony´ıt´ as. 1. l´ep´es: El˝ osz¨ or megadunk egy olyan ε-mentes G1 = (N, Σ, P1 , S) nyelvtant, melyre L(G1 ) = (L(G ) − {ε}).
Defin´ıci´ o. Egy G = (N, Σ, P, S) cf nyelvtan ε-mentes, ha P nem tartalmaz A → ε alak´ u szab´ alyokat, kiv´eve esetleg az S → ε szab´ alyt. Ha azonban S → ε ∈ P, akkor S nem szerepel semelyik P-beli szab´ aly jobb oldal´ an.
Sz´ amoljuk ki a k¨ovetkez˝ o halmazt: H = {A ∈ N | A ⇒∗ ε}.
(Teh´ at ha egy cf nyelvtan ε-mentes, akkor az egyben k¨ornyezetf¨ ugg˝ o is. Erre m´eg visszat´er¨ unk.)
(Azon nemtermin´ alisok halmaza, amelyekb˝ ol levezethet˝ o ε.)
T´ etel. Tetsz˝oleges G = (N, Σ, P, S) cf nyelvtanhoz megkonstru´ alhat´ o vele ekvivalens, (L(G ) = L(G ′ )) ε-mentes ′ ′ ′ G = (N , Σ, P , S ′ ) k¨ornyezetf¨ uggetlen nyelvtan.
Legyen P1 a legsz˝ ukebb olyan szab´ aly-halmaz, melyre teljes¨ ul, hogy
Bizony´ıt´ as. G ′ -t k´et l´ep´esben adjuk meg.
◮
minden olyan A → α ∈ P szab´ aly eset´en melyre α 6= ε,
◮
minden olyan A → α1 szab´ aly P1 -ben van, melyre α1 6= ε ´es α1 u ´gy keletkezik α-b´ ol, hogy elhagyjuk bel˝ ole H-beli nemtermin´ alisok 0 vagy t¨obb el˝ ofordul´ as´ at.
37/127
Cf nyelvtanok ε-mentes´ıt´ese
38/127
Cf nyelvtanok ε-mentes´ıt´ese
P´eld´ aul, ha A, B ∈ H ´es A → aCBbAB ∈ P, akkor az A → aCBbAB, A → aCbAB, A → aCBbB, A → aCBbA, A → aCbB, A → aCbA, A → aCBb, A → aCb szab´ alyok mindegyike P1 -ben lesz.
Az u ´j szab´ alyokkal az eredeti G nyelvtan levezet´eseit szimul´ aljuk, ezen k´ıv¨ ul egy´eb levezet´eseket nem kapunk. Ez´ert
Egy H-beli nemtermin´ alis elhagy´ as´ aval ”megel˝olegezz¨ uk” azt, hogy bel˝ ole ε-t vezet¨ unk le. Pl az A → aCbB u ´j szab´ aly, az
. 2. l´ep´es: A G1 ismeret´eben a k¨ovetkez˝ ok´eppen adjuk meg G ′ -t
L(G1 ) = (L(G ) − {ε})
ul¨onben Ha ε 6∈ L(G ) (vagyis, ha S 6∈ H), akkor legyen G ′ = G1 . K¨ pedig legyen
A ⇒ aCBbAB ⇒∗ aCbAB ⇒∗ aCbB levezet´est reprezent´ alja.
G ′ = (N ∪ {S ′ }, Σ, P1 ∪ {S ′ → S, S ′ → ε}, S ′ ).
Hasonl´ oan, ha C → AB ∈ P, akkor a C → A, C → B ∈ P1 , de C → ε 6∈ P1 .
Nyilv´ anval´o, hogy mindk´et esetben G ′ is ε-mentes, ´es ′ L(G ) = L(G ).
39/127
40/127
Cf nyelvtanok ε-mentes´ıt´ese
Cf nyelvtanok ε-mentes´ıt´ese
P´elda. ε-mentes´ıts¨ uk az al´ abbi G nyelvtant: S A B C
→ → → →
P´elda (folytat´ as). 1. L´ep´es, G1 :
ABC BB | ε CC | a AA | b
S A B C
L´ athat´ o, hogy
→ → → →
ABC | AB | BC | AC | A | B | C BB | B CC | C | a AA | A | b
2. L´ep´es, G ′ :
H = {S, A, C , B}
Mivel ε ∈ L(G ), u ´j kezd˝ oszimb´ olum: S ′ Szab´ alyok: G1 szab´ alyai ´es m´eg S ′ → S | ε.
´es ´ıgy ε ∈ L(G ).
41/127
Cf nyelvtanok ε-mentes´ıt´ese
42/127
Cf nyelvtanok ε-mentes´ıt´ese
Egy fontos ´eszrev´etel:
Nem minden k¨ornyezetf¨ uggetlen nyelvtan k¨ornyezetf¨ ugg˝ o (defin´ıci´o szerint).
Ha egy cf nyelvtant ε-mentes´ıt¨ unk, majd a kapott nyelvtant l´ ancszab´ aly-mentes´ıtj¨ uk, akkor eredm´eny¨ ul egy ε-mentes ´es l´ ancszab´ aly-mentes nyelvtant kapunk.
Ugyanakkor, minden ε-mentes k¨ornyezetf¨ uggetlen nyelvtan k¨ornyezetf¨ ugg˝ o. Ebb˝ol ´es az el˝ oz˝ o t´etelb˝ ol azonnal k¨ovetkezik az al´ abbi.
(Ha az algoritmusokat nem a fenti sorrendben alkalmazzuk, akkor az eredm´eny ´altal´ aban nem l´ ancszab´ aly-mentes nyelvtan lesz, mint ahogy a p´eld´ ab´ ol is l´ athat´ o.)
T´ etel. L2 ⊆ L1 . Bizony´ıt´ as. Legyen L ∈ L2 . Akkor van olyan G = (N, Σ, P, S) cf nyelvtan, melyre L = L(G ). Ha G ε-mentes, akkor egyben k¨ornyezetf¨ ugg˝ o is, teh´ at L ∈ L1 . K¨ ul¨onben, az el˝ oz˝ o t´etel szerint van olyan ε-mentes G ′ cf nyelvtan, melyre L = L(G ′ ). Mivel ekkor G ′ k¨ornyezetf¨ ugg˝ o, u ´jra azt kapjuk, hogy L ∈ L1 .
43/127
44/127
A Chomsky norm´alforma
A Chomsky norm´alforma
Defin´ıci´ o. Egy G = (N, Σ, P, S) k¨ornyezetf¨ uggetlen nyelvtan Chomsky-norm´ alform´ aj´ u (vagy Chomsky norm´ alalakban van), ha ε-mentes ´es P-ben csak S → ε, A → BC ´es A → a alak´ u szab´ alyok vannak.
1. l´ep´es: Megadunk egy G1 = (N1 , Σ, P1 , S) nyelvtant, mely u ekvivalens G -vel, ´es csak S → ε, A → a ´es A → A1 . . . An alak´ szab´ alyokat tartalmaz, ahol a ∈ Σ, n ≥ 2 ´es A, A1 , . . . , An ∈ N1 . Ev´egett legyen
T´ etel. Minden G = (N, Σ, P, S) k¨ornyezetf¨ uggetlen nyelvtanhoz van vele ekvivalens Chomsky-norm´ alform´ aj´ u G ′ = (N ′ , Σ, P ′ , S) k¨ornyezetf¨ uggetlen nyelvtan.
◮ ◮
N1 = N ∪ {a′ | a ∈ Σ} P1 a legsz˝ ukebb halmaz, amire a k¨ovetkez˝ ok teljes¨ ulnek: ◮ ◮
Bizony´ıt´ as. Feltehetj¨ uk, hogy a G nyelvtan ε- ´es l´ ancszab´ aly mentes. Ezek ut´ an G ′ -t k´et l´ep´esben konstru´ aljuk meg.
◮
◮
ha S → ε ∈ P, akkor S → ε ∈ P1 ha A → a ∈ P, akkor A → a ∈ P1 ha A → X1 . . . Xn ∈ P, ahol n ≥ 2, akkor A → X1′ . . . Xn′ ∈ P1 , ahol ( Xi , ha Xi ∈ N Xi′ = a′ , ha Xi = a ∈ Σ minden a ∈ Σ-ra legyen a′ → a ∈ P1 .
Nyilv´ anval´o, hogy L(G ) = L(G1 ).
45/127
A Chomsky norm´alforma
A Chomsky norm´alforma
2. l´ep´es: Most megkonstru´ aljuk G1 -b˝ ol a k´ıv´ ant G ′ = (N ′ , Σ, P ′ , S) nyelvtant. Legyen P ′ a legsz˝ ukebb halmaz, amire az al´ abbiak teljes¨ ulnek: ◮
ha S → ε ∈ P1 , akkor S → ε ∈ P ′ ,
◮
ha A → a ∈ P1 , akkor A → a ∈ P ′ ,
◮
ha A → BC ∈ P1 , akkor A → BC ∈ P ′ ,
◮
46/127
◮
ha A → A1 . . . An (n > 2) ∈ P1 , akkor az A hA2 . . . An i
→ → .. .
A1 hA2 . . . An i, A2 hA3 . . . An i,
hAn−1 An i
→
An−1 An
szab´ alyok P ′ -ben vannak, ahol hA2 . . . An i, . . . , hAn−1 An i u ´j nemtermin´ alisok.
az A → A1 . . . An (n > 2) alak´ u szab´ alyokat pedig “sz´etszedj¨ uk”, ld a k¨ovetkez˝ o di´ at.
Legyen tov´ abb´ a N ′ = N1 ∪ { u ´j nemtermin´ alisok }. ′ Nyilv´ anval´o, hogy G Chomsky-norm´ alalakban van. A bevezetett u ´j szab´ alyokkal csak az eredeti szab´ alyokat tudjuk szimul´ alni, ez´ert L(G ′ ) = L(G1 ). Akinek nem tetszik hA2 . . . An i, hA3 . . . An i, . . . , hAn−1 An i, ´ırhat helyette B2 , B3 , . . . , Bn−1 -et.
47/127
48/127
A Chomsky norm´alforma
Veremautomat´ak
P´elda: hozzuk Chomsky norm´ alform´ ara az S → aSb | ab nyelvtant.
Veremautomat´ anak (vagy pushdown automat´ anak) nevezz¨ uk a P = (Q, Σ, Γ, δ, q0 , Z0 , F ) rendszert, ahol
1. l´ep´es: S a′ b′ ahol
a′
´es
b′
a′ Sb ′ | a′ b ′ a b
→ → →
u ´j nemtermin´ alisok.
2. l´ep´es: S hSb ′ i a′ b′
→ → → →
a′ hSb ′ i | a′ b ′ Sb ′ a b
◮
Q egy v´eges halmaz, az ´ allapotok halmaza;
◮
Σ az input ´ ab´ec´e;
◮
Γ a verem ´ ab´ec´e;
◮
q0 ∈ Q a kezd˝ o´ allapot;
◮
Z0 ∈ Γ a verem kezd˝ oszimb´ olum;
◮
F ⊆ Q a v´eg´ allapotok halmaza;
◮
δ : Q × (Σ ∪ {ε}) × Γ → Pf (Q × Γ∗ ) az ´ atmenet f¨ uggv´eny.
R¨ovid´ıt´es: pda:= veremautomata.
Ez m´ ar Chomsky norm´ alforma. hSb ′ i helyett ´ırhat´ o p´eld´ aul A. 49/127
Veremautomat´ak
50/127
Veremautomat´ak Tetsz˝oleges q ∈ Q, a ∈ (Σ ∪ {ε}) input- ´es Z ∈ Γ veremszimb´ olum eset´en δ(q, a, Z ) = {(q1 , α1 ), . . . , (qn , αn )},
input sz´o
ahol n ≥ 0, q1 , . . . , qn ∈ Q ´es α1 , . . . , αn ∈ Γ∗ . (Az n = 0 esetben δ(q, a, Z ) = ∅.) K´et ´eszrev´etel: 1) Az alap modell nemdeterminisztikus. 2) a = ε is lehets´eges, ami azt fogja jelenteni, hogy a veremautomata nem minden l´ep´esben ”fogyasztja az inputot ”. Az ilyen mozg´ ast ε-mozg´ asnak nevezz¨ uk.
a´llapotok verem
51/127
52/127
Veremautomat´ak
Veremautomat´ak A ⊢P ⊆ C × C a´tmeneti rel´ aci´ o: tetsz˝ oleges p, q ∈ Q, a ∈ (Σ ∪ {ε}), w ∈ Σ∗ , Z ∈ Γ ´es α, γ ∈ Γ∗ -ra
A C = Q × Σ∗ × Γ∗ halmazt a P konfigur´ aci´ oi halmaz´ anak nevezz¨ uk.
(q, aw , Z γ) ⊢P (p, w , αγ)
Egy (q, w , γ) ∈ C konfigur´ aci´ o jelent´ese az, hogy P a q∈Q ´ allapotban van, a w ∈ Σ∗ input sz´ ot kapja ´es verm´enek tartalma γ.
akkor ´es csakis akkor ´ all fenn, ha (p, α) ∈ δ(q, a, Z ). A P = (Q, Σ, Γ, δ, q0 , Z0 , F ) ´ altal v´eg´ allapotokkal felismert nyelv:
A vermet egy sz´ onak tekintj¨ uk. A veremben fel¨ ulr˝ ol sz´ am´ıtott els˝ o, m´ asodik, stb bet˝ u a sz´ o els˝ o, m´ asodik, stb bet˝ uje. P´eld´ aul: AAZ0 az a verem, melyben h´ arom bet˝ u van, a legfels˝ o bet˝ u A.
Lf (P) = {w ∈ Σ∗ | (q0 , w , Z0 ) ⊢∗ (q, ε, γ), ahol q ∈ F , γ ∈ Γ∗ }. AP ´ altal u ¨res veremmel felismert nyelv: L∅ (P) = {w ∈ Σ∗ | (q0 , w , Z0 ) ⊢∗ (q, ε, ε), ahol q ∈ Q}.
A konfigur´ aci´ ot (q, aw , Z γ) alakban is megadhatjuk: az input sz´ o aw , a k¨ovetkez˝ o input a, (ami lehet ε is), a verem tartalma Z γ, a verem tetej´en Z bet˝ u van. 53/127
Veremautomat´ak
54/127
Veremautomat´ak w
w
w
w
⊢∗P q0
⊢∗P γ
q∈F
q0
q∈Q
Z0
Z0
felismer´es u¨res veremmel
felismer´es v´eg´allapotokkal
55/127
56/127
Veremautomat´ak
Veremautomat´ak
P´elda P = (Q, Σ, Γ, δ, q0 , Z0 , F ), ahol
Ugyanez gr´ afk´ent ´ abr´ azolva:
◮
Q = {q0 , q1 , q2 }, Σ = {a, b}, Γ = {a, Z0 }, F = {q0 },
◮
δ pedig a k¨ovetkez˝ o´ atmenetf¨ uggv´eny: ◮ ◮ ◮ ◮ ◮
a, a/aa
δ(q0 , a, Z0 ) = {(q1 , aZ0 )}, δ(q1 , a, a) = {(q1 , aa)}, δ(q1 , b, a) = {(q2 , ε)}, δ(q2 , b, a) = {(q2 , ε)}, δ(q2 , ε, Z0 ) = {(q0 , ε)}.
q0
a, Z0 /aZ0
q1
b, a/ε b, a/ε
q2
ε, Z0 /ε
57/127
Veremautomat´ak
Veremautomat´ak Egy konkr´et P veremautomat´ ara ´ altal´ aban Lf (P) 6= L∅ (P), l´ asd az el˝ oz˝ o p´eld´ at is.
Az aabb input sz´ ora (q0 , aabb, Z0 ) (q2 , b, aZ0 )
⊢ ⊢
58/127
(q1 , abb, aZ0 ) (q2 , ε, Z0 )
⊢ ⊢
(q1 , bb, aaZ0 ) (q0 , ε, ε)
⊢
Ugyanakkor ´erv´enyes a k¨ovetkez˝ o t´etel.
teh´ at aabb ∈ Lf (P). Az abb input sz´ ora
T´ etel. A veremautomat´ akkal v´eg´ allapotokkal felismerhet˝ o nyelvek oszt´alya megegyezik a veremautomat´ akkal u ¨res veremmel felismerhet˝ o nyelvek oszt´ aly´ aval. Vagyis
(q0 , abb, Z0 ) ⊢ (q1 , bb, aZ0 ) ⊢ (q2 , b, Z0 ) ⊢ (q0 , b, ε), mely ut´ obbi konfigur´ aci´ ob´ ol nem lehet tov´ abb menni, teh´ at abb 6∈ Lf (P). Be lehet l´ atni, hogy
{L | L = Lf (P) valamely P veremautomat´ ara } = {L | L = L∅ (P) valamely P veremautomat´ ara }
Lf (P) = {an b n | n ≥ 0} ´es L∅ (P) = {an b n | n ≥ 1}.
59/127
60/127
Veremautomat´ak
Veremautomat´ak
Bizony´ıt´ as. a) Minden P = (Q, Σ, Γ, δ, q0 , Z0 , F ) pda-hoz megkonstru´ alhat´ o olyan P ′ = (Q ′ , Σ, Γ′ , δ′ , q0′ , Z0′ , F ′ ) pda amelyre L∅ (P ′ ) = Lf (P).
Ugyanez lerajzolva: F
Konstrukci´ o: legyen q0′ egy u ´j kezd˝ o´ allapot, qe egy tov´ abbi u ´j ′ allapot, Z0 pedig egy u ´ ´j verem kezd˝ oszimb´ olum. P ′ az els˝ o l´ep´esben egy ε-mozg´ assal ´ atmegy az eredeti q0 kezd˝ o´ allapotba ´es berakja a verembe az eredeti Z0 kezd˝ oszimb´ olumot. Ezut´ an P ′ ut´ anozza P m˝ uk¨ od´es´et. Ha P ′ v´eg´ allapotba ker¨ ul, akkor P egy ε-mozg´ assal ´ atmegy a qe allapotba, amiben ki¨ ´ ur´ıti a vermet. Ha P felismer, akkor P ′ is felismer. Z0′ -re az´ert van sz¨ uks´eg, mert ha P verme ki¨ ur¨ ul, (ami P eset´eben nem jelent felismer´est) akkor P ′ verm´eben bennmarad Z0′ , teh´ at P ′ sem ismer fel.
q0′
ε, Z0′ /Z0 Z0′
q0
q
ε, Z /ε
ε, Z /ε
qe
62/127
61/127
Veremautomat´ak
Veremautomat´ak Az L∅ (P ′ ) = Lf (P) bizony´ıt´ asa:
Az el˝ oz˝ o form´alisan. Legyen ◮
Q ′ = Q ∪ {q0′ , qe }, ahol q0′ ´es qe u ´j ´ allapotok;
◮ Γ′ ◮ ◮
=Γ∪
{Z0′ },
ahol
Z0′
⇐⇒ ⇐⇒
egy u ´j szimb´ olum;
F ′ tetsz˝ oleges r´eszhalmaza Q ′ -nek; (1) δ ′ (q0′ , ε, Z0′ ) = {(q0 , Z0 Z0′ )}, (2) minden q ∈ Q, a ∈ (Σ ∪ {ε}), Z ∈ Γ eset´en δ(q, a, Z ) ∪ {(qe , ε)} ha a = ε ´es q ∈ F ′ δ (q, a, Z ) = δ(q, a, Z ) ha a 6= ε vagy q 6∈ F
w ∈ Lf (P) (q0 , w , Z0 ) (q0′ , w , Z0′ )
⊢∗P ⊢P ′ ⊢∗P ′ = ⊢P ′ ⊢∗P ′
(q, ε, γ) ahol q ∈ F (q0 , w , Z0 Z0′ ) (q, ε, γZ0′ ) ahol q ∈ F (q, ε, Z1 . . . Zk Z0′ ) (qe , ε, Z2 . . . Zk Z0′ ) (qe , ε, ε)
(def. szerint) ((1) miatt) ((2) miatt) (γ = Z1 . . . Zk ) ((2) miatt) ((3) miatt)
⇐⇒ w ∈ L∅ (P ′ )
(def. szerint).
(3) minden Z ∈ Γ′ -re δ ′ (qe , ε, Z ) = {(qe , ε)}.
63/127
64/127
Veremautomat´ak
Veremautomat´ak
b) Minden P = (Q, Σ, Γ, δ, q0 , Z0 , F ) pda-hoz megkonstru´ alhat´ o olyan P ′ = (Q ′ , Σ, Γ′ , δ′ , q0′ , Z0′ , F ′ ) pda amelyre Lf (P ′ ) = L∅ (P)
Ugyanez lerajzolva:
Konstrukci´ o: legyen q0′ egy u ´j kezd˝ o´ allapot, qf egy u ´j v´eg´ allapot, ′ Z0 pedig egy u ´j verem kezd˝ oszimb´ olum. P ′ az els˝ o l´ep´esben egy ε-mozg´ assal ´ atmegy az eredeti q0 kezd˝ o´ allapotba ´es berakja a verembe az eredeti Z0 kezd˝ oszimb´ olumot. Ezut´ an P ′ ut´ anozza P m˝ uk¨ od´es´et. Ha P verme ki¨ ur¨ ul, akkor P ′ verm´eben bennmarad Z0′ . Ekkor P ′ egy ε-mozg´ assal ´ atmegy a qf v´eg´ allapotba. Ha P felismer, akkor P ′ is felismer. Z0′ -re az´ert van sz¨ uks´eg, mert ha ˝ o van a verem tetej´en, akkor tudjuk, hogy P verme ki¨ ur¨ ult.
q0′
ε, Z0′ /Z0 Z0′
q0
q
ε, Z0′ /ε
qf
66/127
65/127
Veremautomat´ak
Veremautomat´ak Lf (P ′ ) = L∅ (P), mert:
Az el˝ oz˝ o form´alisan. Legyen ◮
Q ′ = Q ∪ {q0′ , qf }, ahol q0′ ´es qf u ´j ´ allapotok;
◮ Γ′ ◮ ◮
=Γ∪
{Z0′ },
ahol
Z0′
⇐⇒ ⇐⇒
egy u ´j szimb´ olum;
F ′ = {qf }; δ′ az al´ abbi m´ odon defini´ alt ´ atmenetf¨ uggv´eny:
w ∈ L∅ (P) (q0 , w , Z0 ) (q0′ , w , Z0′ )
⊢∗P ⊢P ′ ⊢∗P ′ ⊢P ′
(q, ε, ε) ahol q ∈ Q (q0 , w , Z0 Z0′ ) (q, ε, Z0′ ) ahol q ∈ Q (qf , ε, ε)
(def. szerint) ((1) miatt) ((2) miatt) ((3) miatt)
⇐⇒
(1) δ ′ (q0′ , ε, Z0′ ) = {(q0 , Z0 Z0′ )}, (2) minden q ∈ Q, a ∈ (Σ ∪ {ε}), Z ∈ Γ eset´en δ ′ (q, a, Z ) = δ(q, a, Z ), (3) minden q ∈ Q eset´en, δ ′ (q, ε, Z0′ ) = {(qf , ε)}.
w ∈ Lf (P ′ )
67/127
(def. szerint).
68/127
A cf nyelvtanok ´es a pda-k ekvivalenci´aja
A cf nyelvtanok ´es a pda-k ekvivalenci´aja
T´ etel. Minden cf nyelv felismerhet˝ o pda-val. Az ¨otlet az, hogy a kapott veremautomat´ aval a nyelvtan bal oldali levezet´eseit szimul´ aljuk.
Bizony´ıt´ as. Vegy¨ unk egy G = (N, Σ, R, S) k¨ornyezetf¨ uggetlen nyelvtant. Legyen P = ({q}, Σ, Γ, δ, q, Z0 , ∅) az a veremautomata, amelyben ◮
Γ = N ∪ Σ,
◮
Z0 = S, δ´ atmenetf¨ uggv´eny pedig a k¨ovetkez˝o m´ odon van defini´ alva:
◮
Ha a verem tetej´en egy A nemtermin´ alis van, akkor az inputban nem olvasunk tov´ abb (ε-mozg´ as) ´es a verembe az A hely´ere betessz¨ uk egy A bal oldal´ u szab´ aly jobb oldal´ at. (Pl, ha A → α egy szab´ aly, akkor A hely´ere α-t.) Ha a verem tetej´en egy a termin´ alis van ´es az input els˝ o bet˝ uje is a, akkor az inputban elolvassuk, a veremb˝ ol pedig t¨or¨ olj¨ uk a-t.
(1) minden A ∈ N-re δ(q, ε, A) = {(q, α) | A → α ∈ R}, (2) minden a ∈ Σ-ra δ(q, a, a) = {(q, ε)}.
Legyen w egy input sz´ o. Ha w ∈ L(G ), akkor, mivel a veremben kezdetben S van ´es a nemdeterminizmus miatt minden lehet˝ os´eget kipr´ ob´ alunk, a veremautomata ”meg fogja tal´ alni” w -nek egy bal oldali levezet´es´et ´es ezzel ki¨ ur´ıti a vermet. Ha w 6∈ L(G ), akkor, S-b˝ ol nem vezethet˝ o le w , ez´ert e verem soha nem u ¨r¨ ul ki.
´ Eszrev´ etel: egyetlen ´ allapot elegend˝ o!
69/127
A cf nyelvtanok ´es a pda-k ekvivalenci´aja
A cf nyelvtanok ´es a pda-k ekvivalenci´aja I. F.: minden 1 ≤ i ≤ k eset´en (q, wi , Xi ) ⊢∗ (q, ε, ε). Innen kapjuk, hogy
Megmutatjuk, hogy L∅ (P) = L(G ). Elegend˝ o igazolni, hogy ∗ minden X ∈ (N ∪ Σ) ´es w ∈ Σ eset´en X ⇒∗ w akkor ´es csakis akkor, ha (q, w , X ) ⊢∗ (q, ε, ε)
(q, w , X )
(a) Tfh X ⇒n w (i) n = 0: X = w ∈ Σ, ez´ert a (2) pont szerint
(ii) n=⇒n + 1: X ⇒ X1 . . . Xk
= ⊢ ⊢∗ ⊢∗ ⊢∗
(q, w , X ) = (q, w , w ) ⊢ (q, ε, ε). ⇒n
70/127
(q, w1 . . . wk , X ) (q, w1 . . . wk , X1 . . . Xk ) (q, w2 . . . wk , X2 . . . Xk ) ... (q, wk , Xk ) (q, ε, ε).
A felismer´es sor´ an P a w -nek egy bal oldali levezet´es´et szimul´ alja. ∗ (b) Tfh (q, w , X ) ⊢ (q, ε, ε). Az ´ atmenetek sor´ an alkalmazott (1) t´ıpus´ u´ atmenetek sz´ ama szerinti indukci´ oval igazolhatjuk, hogy X ⇒∗ w .
w1 . . . wk = w
1) X → X1 . . . Xk ∈ R 2) Xi ⇒ni wi minden 1 ≤ i ≤ k-ra, ahol ni ≤ n
71/127
72/127
A cf nyelvtanok ´es a pda-k ekvivalenci´aja
A cf nyelvtanok ´es a pda-k ekvivalenci´aja
P´elda. Par a k¨ovetkez˝ ok´eppen ismeri fel az a + a ∈ L(Gar ) sz´ ot: A Gar nyelvtanhoz a k¨ovetkez˝ o Par = ({q}, Σ, Γ, δ, q, K , ∅) veremautomat´ at konstru´ aljuk: ◮
Σ = {a, +, ∗, (, )},
◮
Γ = {K , T , F , a, +, ∗, (, )}, δ pedig a k¨ovetkez˝ o´ atmenet f¨ uggv´eny:
◮
◮ ◮ ◮ ◮
(q, a + a, K ) (q, a + a, a + T ) (q, a, F )
⊢ ⊢ ⊢
(q, a + a, K + T ) (q, +a, +T ) (q, a, a)
⊢2 ⊢ ⊢
(q, a + a, F + T ) (q, a, T ) (q, ε, ε)
⊢ ⊢
Ez a
δ(q, ε, K ) = {(q, K + T ), (q, T )}, δ(q, ε, T ) = {(q, T ∗ F ), (q, F )}, δ(q, ε, F ) = {(q, (K )), (q, a)}, minden x ∈ {a, +, ∗, (, )} eset´en δ(q, x, x) = {(q, ε)}.
K ⇒l K + T ⇒2l F + T ⇒l a + T ⇒l a + F ⇒l a + a bal oldali levezet´esnek felel meg.
73/127
A cf nyelvtanok ´es a pda-k ekvivalenci´aja
74/127
A cf nyelvtanok ´es a pda-k ekvivalenci´aja
T´ etel. Minden pda-val felismerhet˝ o nyelv k¨ornyezetf¨ uggetlen. ◮
Bizony´ıt´ as. Legyen P = (Q, Σ, Γ, δ, q0 , Z0 , F ) egy pda.
(1) minden q ∈ Q-ra legyen S → [q0 Z0 q] szab´aly R-ben,
Konstru´ aljuk meg a G = (N, Σ, R, S) cf nyelvtant a k¨ovetkez˝ ok´eppen. ◮
Legyen S egy u ´j szimb´ olum,
◮
legyen N = {S} ∪ {[qZr ] | q, r ∈ Q, Z ∈ Γ},
legyen R szab´ alyok legsz˝ ukebb olyan halmaza, amire teljes¨ ulnek a k¨ovetkez˝ o felt´etelek:
(2) minden q ∈ Q, a ∈ (Σ ∪ {ε}), Z ∈ Γ-ra, ha (s0 , Z1 . . . Zk ) ∈ δ(q, a, Z ), (ahol k ≥ 1, Z1 , . . . , Zk ∈ Γ) akkor minden s1 , . . . , sk ∈ Q sorozatra legyen [qZsk ] → a[s0 Z1 s1 ] . . . [sk−1 Zk sk ] szab´aly R-ben, (3) minden q ∈ Q, a ∈ (Σ ∪ {ε}), Z ∈ Γ-ra, ha (s0 , ε) ∈ δ(q, a, Z ), akkor legyen [qZs0 ] → a szab´aly R-ben (az el˝ oz˝o eset k = 0-ra).
Egy [qZr ] h´ armas intuit´ıv jelent´ese az, hogy ha a pda q ´ allapotban van, a verem legfels˝ o szimb´ oluma Z , akkor az r ´ allapotba jutva tudja kivenni (t¨or¨ olni) Z -t a veremb˝ ol.
Megmutatjuk, hogy L(G ) = L∅ (P).
75/127
76/127
A cf nyelvtanok ´es a pda-k ekvivalenci´aja
A cf nyelvtanok ´es a pda-k ekvivalenci´aja
Elegend˝ o megmutatni, hogy minden q, r ∈ Q, Z ∈ Γ ´es w ∈ Σ∗ eset´en
(a) Tfh [qZr ] ⇒n w valamilyen n ≥ 1-re. ´gy lehet, ha w = a ∈ (Σ ∪ {ε}) ´es (i) n = 1: [qZr ] ⇒ w , ez csak u (r , ε) ∈ δ(q, a, Z ). Teh´ at (q, w , Z ) = (q, a, Z ) ⊢ (r , ε, ε). (ii) n=⇒n + 1:
(q, w , Z ) ⊢∗ (r , ε, ε) akkor ´es csak akkor, ha [qZr ] ⇒∗ w . Ugyanis ezen ekvivalencia a q = q0 ´es Z = Z0 esetben ´eppen az L(G ) = L∅ (P) egyenl˝os´eget jelenti:
⇔ ⇔ ⇔ ⇔
[qZr ] ⇒ a[s0 Z1 s1 ] . . . [sk−1 Zk sk ] ⇒n aw1 . . . wk = w
w ∈ L∅ (P) (q0 , w , Z0 ) ⊢∗ (r , ε, ε) [q0 Z0 r ] ⇒∗ w S ⇒ [q0 Z0 r ] ⇒∗ w w ∈ L(G )
1) [qZr ] → a[s0 Z1 s1 ] . . . [sk−1 Zk sk ] ∈ R, r = sk , azaz (s0 , Z1 . . . Zk ) ∈ δ(q, a, Z ) 2) Minden 1 ≤ i ≤ k-ra [si −1 Zi si ] ⇒ni wi , ´es ni ≤ n.
77/127
A cf nyelvtanok ´es a pda-k ekvivalenci´aja
A cf nyelvtanok ´es a pda-k ekvivalenci´aja
I. F.: minden 1 ≤ i ≤ k-ra (si −1 , wi , Zi ) ⊢∗ (si , ε, ε). Kapjuk, hogy (q, w , Z )
= ⊢ ⊢∗ ⊢∗ ⊢∗ =
78/127
P´elda. Alkalmazzuk az el˝ oz˝ o lemm´ aban szerepl˝ o konstrukci´ ot az {an b n | n ≥ 1} nyelvet u ¨res veremmel felismer˝ o veremautomat´ ara:
(q, aw1 . . . wk , Z ) (s0 , w1 . . . wk , Z1 . . . Zk ) (s1 , w2 . . . wk , Z2 . . . Zk ) ... (sk−1 , wk , Zk ) (sk , ε, ε) (r , ε, ε)
a, a/aa
q0
Az ekvivalencia megford´ıt´ as´ at hasonl´ o m´ odon, a (q, w , Z ) ⊢n (r , ε, ε) felt´etelben szerepl˝o n szerinti indukci´ oval bizony´ıthatjuk be.
a, Z0 /aZ0
q1
b, a/ε b, a/ε
q2
ε, Z0 /ε
79/127
80/127
A cf nyelvtanok ´es a pda-k ekvivalenci´aja
A cf nyelvtanok ´es a pda-k ekvivalenci´aja
P´elda (folyt).
P´elda (folyt).
Egy olyan G nyelvtant kapunk, melynek szab´ alyai a k¨ovetkez˝ ok:
Azonban k¨onnyen bel´ athat´ o, hogy a fenti 24 szab´ aly k¨oz¨ ul csak az al´ abbi 6 szerepel valamely {a, b}∗ -beli sz´ o levezet´es´eben:
◮
S → [q0 Z0 qi ], minden 0 ≤ i ≤ 2-re
◮
[q0 Z0 qj ] → a[q1 aqi ][qi Z0 qj ], minden 0 ≤ i , j ≤ 2-re
◮
S → [q0 Z0 q0 ]
[q1 aqj ] → a[q1 aqi ][qi aqj ], minden 0 ≤ i , j ≤ 2-re
◮
[q0 Z0 q0 ] → a[q1 aq2 ][q2 Z0 q0 ]
◮
[q1 aq2 ] → b
◮
[q1 aq2 ] → a[q1 aq2 ][q2 aq2 ]
◮
[q2 aq2 ] → b
◮
[q1 aq2 ] → b
◮
[q2 Z0 q0 ] → ε.
◮
[q2 aq2 ] → b
◮
[q2 Z0 q0 ] → ε.
◮
¨ Osszesen 24 szab´ aly! Err˝ ol a nyelvtanr´ol m´ ar k¨onnyen bel´ athat´ o, hogy az {an b n | n ≥ 1} nyelvet gener´ alja. 82/127
81/127
A cf nyelvtanok ´es a pda-k ekvivalenci´aja
A Chomsky nyelvoszt´alyok g´epi reprezent´aci´oi
¨ Osszefoglal´ as: G´epi reprezent´ aci´ o: A k¨ovetkez˝ o eszk¨oz¨ ok mindegyik´evel pontosan a k¨ornyezetf¨ uggetlen nyelveket reprezent´ alhatjuk: ◮
k¨ornyezetf¨ uggetlen (2-t´ıpus´ u) nyelvtanok,
◮
v´eg´ allapotokkal felismer˝ o veremautomat´ ak,
◮
u ¨res veremmel felismer˝ o veremautomat´ ak.
Nyelvoszt´ aly L3 (regul´ aris nyelvek) L2 (k. f¨ uggetlen nyelvek) L1 (k. f¨ ugg˝ o nyelvek) L0 (´ altal´ anos nyelvek)
G´epi repr. v´eges automat´ ak veremautomat´ ak ? ?
Det. vs nemdet. det. = nemdet. det. ⊂ nemdet. ? ?
A val´odi tartalmaz´ ast k´es˝ obb bizony´ıtjuk.
83/127
84/127
Determinisztikus veremautomat´ak
Determinisztikus veremautomat´ak
Defin´ıci´ o. Egy P = (Q, Σ, Γ, δ, q0 , Z0 , F ) veremautomata o k´et determinisztikus, ha minden q ∈ Q-ra ´es Z ∈ Γ-ra a k¨ovetkez˝ felt´etel valamelyike teljes¨ ul:
Felismer˝ o kapacit´ as? T´ etel. Minden regul´ aris nyelv felismerhet˝ o determinisztikus veremautomat´ aval v´eg´ allapotokkal. Bizony´ıt´ as. Legyen M = (Q, Σ, δ, q0 , F ) egy (determinisztikus) automata. Konstru´ aljuk meg a P = (Q, Σ, {Z0 }, δ′ , q0 , Z0 , F ) veremautomat´ at, melyre minden p, q ∈ Q ´es a ∈ Σ eset´en
(1) δ(q, ε, Z ) = ∅ ´es minden a ∈ Σ-ra a δ(q, a, Z ) halmaz legfeljebb egy elem˝ u, vagy (2) minden a ∈ Σ-ra δ(q, a, Z ) = ∅ ´es a δ(q, ε, Z ) halmaz legfeljebb egy elem˝ u.
δ(q, a) = p ⇐⇒ δ′ (q, a, Z0 ) = (p, Z0 ).
A felt´etel garant´ alja, hogy minden (q, aw , Z γ) konfigur´ aci´ ohoz legfeljebb egy olyan (p, w , αγ) konfigur´aci´ o van, amelyre
Nyilv´ anval´o, hogy P determinisztikus ´es Lf (P) = L(M).
(q, aw , Z γ) ⊢P (p, w , αγ)! P´elda: az {an b n | n ≥ 0} nyelvet felismer˝ o veremautomata determinisztikus. 85/127
Determinisztikus veremautomat´ak
86/127
Determinisztikus veremautomat´ak
Felismer˝ o kapacit´ as?
Felismer˝ o kapacit´ as?
T´ etel. Van olyan v´eges nyelv, amely nem ismerhet˝ o fel determinisztikus veremautomat´ aval u ¨res veremmel.
Teh´ at, a determinisztikus veremautomat´ ak eset´eben csak a v´eg´allapotokkal val´o felismer´es hat´ekony. A determinisztikus veremautomat´ akkal v´eg´ allapotokkal felismerhet˝ o nyelveket determinisztikus nyelveknek nevezz¨ uk. A olj¨ uk. determinisztikus nyelvek oszt´ aly´ at Ld -vel jel¨
Bizony´ıt´ as. Legyen p´eld´ aul L = {a, ab} ´es tegy¨ uk fel, hogy L = L∅ (P) valamely P = (Q, Σ, Γ, δ, q0 , Z0 , F ) determinisztikus veremautomat´ ara. (q0 , a, Z0 ) ⊢∗P
T´ etel. L3 ⊂ Ld ⊂ L2 .
(q0 , ab, Z0 ) ⊢∗P
Akkor (p, ε, ε) ´es (q, ε, ε) valamely p, q ∈ Q-ra. De akkor a determinisztikuss´ag miatt
Bizony´ıt´ as. Az els˝ o tartalmaz´ as: mint l´ attuk, minden regul´ aris nyelv determinisztikus, az {an b n | n ≥ 0} nyelv pedig determinisztikus, de nem regul´ aris. Az m´ asodik tartalmaz´ ast k´es˝ obb bizony´ıtjuk.
(q0 , ab, Z0 ) ⊢∗P (p, b, ε) ⊢∗P (q, ε, ε), ami lehetetlen, mert u ¨res verem eset´en nincs r´ ak¨ovetkez˝ o konfigur´ aci´ o. 87/127
88/127
Determinisztikus veremautomat´ak
Pump´al´o lemma k¨ornyezetf¨uggetlen nyelvekre, vagy Bar–Hillel lemma
Bizony´ıt´ as n´elk¨ ul:
T´ etel. Minden L ⊆ Σ∗ k¨ornyezetf¨ uggetlen nyelvhez
T´ etel. Minden determinisztikus nyelv egy´ertelm˝ u (vagyis gener´ alhat´ o egy´ertelm˝ u cf nyelvtannal).
- megadhat´ o olyan (L-t˝ol f¨ ugg˝ o) k > 0 eg´esz sz´ am, hogy - minden w ∈ L eset´en, - ha |w | ≥ k, akkor van olyan w = w1 w2 w3 w4 w5 felbont´ as, melyre:
Bizony´ıt´ as. (V´ azlat.) Konstru´ aljuk meg a nyelvet felismer˝ o determinisztikus pda-b´ol az ekvivalens cf nyelvtant a megismert m´ odon. Meg lehet mutatni, hogy az ´ıgy kapott nyelvtan egy´ertelm˝ u.
1) |w2 w3 w4 | ≤ k, 2) w2 w4 6= ε, 3) minden n ≥ 0-ra, w1 w2n w3 w4n w5 ∈ L. (Sz¨ uks´eges felt´etele annak, hogy egy nyelv cf legyen.)
89/127
Pump´al´o lemma k¨ornyezetf¨uggetlen nyelvekre, vagy Bar–Hillel lemma
90/127
Pump´al´o lemma k¨ornyezetf¨uggetlen nyelvekre, vagy Bar–Hillel lemma Ha ugyanis h(t) ≤ m lenne, akkor a t deriv´ aci´ os fa mindegyik u ´tj´ an legfeljebb m nemtermin´ alis lenne (a legals´o cs´ ucsponton termin´ alis van).
Bizony´ıt´ as. Legyen L = L(G ), ahol G = (N, Σ, P, S) Chomsky-norm´ alform´ aban l´ev˝ o cf nyelvtan. Legyen k = 2m , ahol m = ||N||. Megmutatjuk, hogy ez a k megfelel˝o lesz.
Mivel (Chomsky-norm´ alforma miatt) a fa minden nemtermin´ alis cs´ ucspontban legfeljebb k´etfel´e ´ agazik, a legals´o nemtermin´ alisn´ al pedig m´ar nem ´ agazik el, a w sz´ o hossza legfeljebb 2m−1 lenne.
Vegy¨ unk egy w ∈ L sz´ ot, melyre |w | ≥ k. Akkor van olyan t ∈ DS deriv´ aci´ os fa, melyre fr (t) = w ´es h(t) ≥ m + 1.
K¨ovetkez´esk´eppen t-ben van olyan, S-t˝ol valamely lev´elhez vezet˝ o u ´t melynek hossza legal´ abb m + 1 ´es amelyen ez´ert (egy termin´ alis ´es) legal´ abb m + 1 nemtermin´ alis szimb´ olum szerepel.
91/127
92/127
Pump´al´o lemma k¨ornyezetf¨uggetlen nyelvekre, vagy Bar–Hillel lemma
Pump´al´o lemma k¨ornyezetf¨uggetlen nyelvekre, vagy Bar–Hillel lemma Mivel m = ||N||, van olyan nemtermin´ alis, ami ezen az u ´ton alist, amelyik legal´ abb k´etszer el˝ ofordul. Jel¨ olje A azt a nemtermin´ a termin´alis lev´elt˝ ol indulva a gy¨ ok´er fel´e legel˝osz¨ or megism´etl˝ odik.
S
t
Defini´ aljuk w1 , w2 , w3 , w4 ´es w5 szavakat az ´ abr´ an l´ athat´ o m´ odon. ar´ at osztottuk fel. Ekkor nyilv´ an w = w1 w2 w3 w4 w5 , mert t hat´ Tov´abb´ a:
A t′ A
1) |w2 w3 w4 | ≤ k, mert a legels˝o ism´etl˝ od´est vett¨ uk, 2) w2 w4 6= ε, mert az A ”fels˝ o” el˝ ofordul´ as´ an´ al a fa k´etfel´e agazik ´es egyik ´ ´ agon sem vezethet˝ o le ε (Chomsky-norm´ alforma!),
t ′′
w1
w2
w3
3) minden n ≥ 0-ra, w1 w2n w3 w4n w5 ∈ L, mert a t ′ fa iter´ alhat´ o.
w5 = w
w4
93/127
Pump´al´o lemma k¨ornyezetf¨uggetlen nyelvekre, vagy Bar–Hillel lemma 0
Pump´al´o lemma k¨ornyezetf¨uggetlen nyelvekre, vagy Bar–Hillel lemma Egy k¨ovetkezm´eny:
1 A
A
T´ etel. Az L = {an b n c n | n ≥ 1} nyelv nem k¨ornyezetf¨ uggetlen.
A
Bizony´ıt´ as. Tfh igen. A Bar Hillel lemma szerint van olyan k > 0 sz´ amok, hogy minden w ∈ L sz´ ora, ha |w | ≥ k, akkor teljes¨ ulnek ezen lemm´ aban szerepl˝ o 1) – 3) felt´etelek.
w3
w5
w1
94/127
w1 w2
w3
w4
w5
Vegy¨ uk az ak b k c k ∈ L sz´ ot, aminek a hossza 3k ≥ k. A pump´ al´ o lemma szerint l´etezik ak b k c k = w1 w2 w3 w4 w5 felbont´ as, melyre a 2) ´es 3) felt´etel szerint: w2 w4 6= ε, ´es minden n ≥ 0-ra w1 w2n w3 w4n w5 ∈ L.
2 A ... A
A w1 w2
w4 w5
95/127
96/127
Pump´al´o lemma k¨ornyezetf¨uggetlen nyelvekre, vagy Bar–Hillel lemma
Pump´al´o lemma k¨ornyezetf¨uggetlen nyelvekre, vagy Bar–Hillel lemma
Teh´ at ak b k c k = w1 w2 w3 w4 w5 , w2 w4 6= ε, ´es minden n ≥ 0-ra w1 w2n w3 w4n w5 ∈ L.
Egy inform´ alis megjegyz´es: Az {an b n | n ≥ 1} nyelv k¨ornyezetf¨ uggetlen, de az {an b n c n | n ≥ 1} nyelv nem.
Hogyan helyezkedhet w2 ´es w4 az ak b k c k sz´ oban? Sem w2 sem w4 nem tartalmazhat k´et k¨ ul¨onb¨oz˝ o bet˝ ut, mert ekkor p´eld´ aul a w1 w22 w3 w42 w5 sz´ oban a bet˝ uk sorrendje nem a − b − c lenne! Teh´ at mind w2 mind w4 legfeljebb egy fajta bet˝ ut tartalmaz. Akkor viszont a w1 w22 w3 w42 w5 sz´ oban legal´ abb egy ´es legfeljebb k´et fajta bet˝ unek a sz´ ama t¨obb, mint a harmadik fajta bet˝ u´e.
A k¨ornyezetf¨ uggetlen nyelvtan k´epes sz´ amolni ”k´et valamit”, de nem k´epes sz´ amolni ”h´ arom valamit”.
Teh´ at w1 w22 w3 w42 w5 6∈ L.
97/127
Pump´al´o lemma k¨ornyezetf¨uggetlen nyelvekre, vagy Bar–Hillel lemma
98/127
K¨ornyezetf¨uggetlen nyelvek z´arts´agi tulajdons´agai
Egy tov´ abbi k¨ovetkezm´eny: van olyan k¨ornyezetf¨ ugg˝ o nyelv, amelyik nem k¨ornyezetf¨ uggetlen.
Regul´ aris m˝ uveletek T´ etel. A cf nyelvek oszt´ alya z´ art a regul´ aris m˝ uveletekre n´ezve. Bizony´ıt´ as. Legyenek G1 = (N1 , Σ, P1 , S1 ) ´es G2 = (N2 , Σ, P2 , S2 ) cf nyelvtanok, L1 = L(G1 ) ´es L2 = L(G2 ).
T´ etel. L2 ⊂ L1 . Bizony´ıt´ as. Azt m´ ar l´ attuk, hogy L2 ⊆ L1 (ε-mentes´ıt´es). n n n L = {a b c | n ≥ 1} ∈ L1 (k¨ornyezetf¨ ugg˝ o), mert a k¨ovetkez˝ o nyelvtan gener´ alja:
a) egyes´ıt´es: Legyen G = (N1 ∪ N2 ∪ {S}, Σ, P1 ∪ P2 ∪ {S → S1 , S → S2 }, S), ahol S egy u ´j szimb´ olum. Akkor L(G ) = L1 ∪ L2 .
S → SC1 A → aAB1 BC3 → BC BB2 → BB1 C2 C → C1 C
S → AC1 B1 C1 → B1 C3 B1 B → B1 B2 CC1 → C2 C1 B→b
b) konkaten´ aci´ o: Legyen G = (N1 ∪ N2 ∪ {S}, Σ, P1 ∪ P2 ∪ {S → S1 S2 }, S). Akkor L(G ) = L1 L2 .
A → aB1 B1 C3 → BC3 B1 B2 → BB2 C2 C1 → C2 C C →c
c) iter´ aci´ o: Legyen G = (N1 ∪ {S}, Σ, P1 ∪ {S → S1 S, S → ε}, S). Akkor L(G ) = L∗1 .
Ugyanakkor L 6∈ L2 . 99/127
100/127
K¨ornyezetf¨uggetlen nyelvek z´arts´agi tulajdons´agai
K¨ornyezetf¨uggetlen nyelvek z´arts´agi tulajdons´agai b) komplementer: Legyenek L1 ⊆ Σ∗ ´es L2 ⊆ Σ∗ k¨ornyezetf¨ uggetlen nyelvek.
Boole m˝ uveletek T´ etel. A cf nyelvek oszt´ alya nem z´ art sem a metszetre sem a komplementerre (ugyanakkor z´ art az egyes´ıt´esre).
A de Morgan azonoss´ ag szerint L1 ∩ L2 = L1 ∪ L2 . Tov´ abb´ a, a k¨ornyezetf¨ uggetlen nyelvek oszt´ alya z´ art az egyes´ıt´esre.
Bizony´ıt´ as. a) metszet: L1 = {am b m c n | m, n ≥ 0} cf, mert gener´ alhat´ o az al´ abbi k¨ornyezetf¨ uggetlen nyelvtannal: S → AB A → aAb|ε B → cB|ε Hasonl´ oan l´ athat´ o be, hogy az L2 = {am b n c n | m, n ≥ 0} is k¨ornyezetf¨ uggetlen. Ugyanakkor L1 ∩ L2 = {an b n c n | n ≥ 0}, ami nem cf.
Ez´ert, ha a komplementer k´epz´esre is z´ art lenne, akkor a metszetre is z´art lenne. K¨ ovetkezm´ eny. A determinisztikus cf nyelvek oszt´ alya nem z´ art a metszetre. Bizony´ıt´ as. Az el˝ oz˝ o bizony´ıt´ asban szerepl˝ o L1 ´es L2 nyelvek val´oj´ aban determinisztikus cf nyelvek.
101/127
K¨ornyezetf¨uggetlen nyelvek z´arts´agi tulajdons´agai
102/127
K¨ornyezetf¨uggetlen nyelvek z´arts´agi tulajdons´agai
Metszet regul´ aris nyelvvel ◮
T´ etel. A cf nyelvek oszt´ alya z´ art regul´aris nyelvvel val´o metszetre. (Ha L k¨ornyezetf¨ uggetlen, L′ pedig regul´ aris nyelv, akkor L ∩ L′ k¨ornyezetf¨ uggetlen.)
Minden p, q ∈ Q, p ′ , q ′ ∈ Q ′ , a ∈ Σ, Z ∈ Γ ´es γ ∈ Γ∗ eset´en, ¯ ((p, p ′ ), γ) ∈ δ((q, q ′ ), a, Z ) akkor ´es csak akkor, ha (p, γ) ∈ δ(q, a, Z ) ´es p ′ = δ′ (q ′ , a),
Bizony´ıt´ as. Legyen L = Lf (P) egy k¨ornyezetf¨ uggetlen nyelv, ahol P = (Q, Σ, Γ, δ, q0 , Z0 , F ) egy veremautomata ´es L′ = L(M) egy regul´ aris nyelv, ahol M = (Q ′ , Σ, δ′ , q0′ , F ′ ) egy determinisztikus automata. ¯ = (Q × Q ′ , Σ, Γ, δ, ¯ (q0 , q ′ ), Z0 , F × F ′ ) Megkonstru´ aljuk a P 0 veremautomat´ at, ahol a δ¯ : (Q × Q ′ ) × (Σ ∪ {ε}) × Γ → Pf ((Q × Q ′ ) × Γ∗ ) atmenetf¨ ´ uggv´enyt a k¨ovetkez˝ ok´eppen defini´ aljuk:
◮
Minden p, q ∈ Q, q ′ ∈ Q ′ , Z ∈ Γ ´es γ ∈ Γ∗ eset´en, ¯ ((p, q ′ ), γ) ∈ δ((q, q ′ ), ε, Z ) akkor ´es csak akkor, ha (p, γ) ∈ δ(q, ε, Z ).
A konstrukci´ o hasonl´ o az automat´ ak direkt szorzata konstrukci´ ohoz.
103/127
104/127
K¨ornyezetf¨uggetlen nyelvek z´arts´agi tulajdons´agai
K¨ornyezetf¨uggetlen nyelvek z´arts´agi tulajdons´agai
¯ = L ∩ L′ bizony´ıt´ Az Lf (P) asa (v´ azlat). Elegend˝ o megmutatni, hogy minden p, q ∈ Q, p ′ , q ′ ∈ Q ′ , Z ∈ Γ, γ ∈ Γ∗ ´es x ∈ Σ∗ eset´en, ((q, q ′ ), x, Z ) ⊢∗P¯ ((p, p ′ ), ε, γ)
¯ is determinisztikus, teh´ Ha P determinisztikus, akkor P at: K¨ ovetkezm´ eny. A determinisztikus cf nyelvek oszt´ alya z´ art regul´ aris nyelvvel val´o metszetre.
akkor ´es csak akkor, ha (q, x, Z ) ⊢∗P (p, ε, γ) ´es (q ′ , x) ⊢∗M (p ′ , ε). ´Igy
¯ x ∈ L(P)
⇐⇒
((q0 , q0′ ), x, Z0 ) ⊢∗P¯ ((p, p ′ ), ε, γ), v.mely (p, p ′ ) ∈ (F × F ′ )-re
⇐⇒
(q0 , x, Z0 ) ⊢∗P (p, ε, γ) valamely p ∈ F -re ´es (q0′ , x) ⊢∗M (p ′ , ε) valamely p ′ ∈ F ′ -re
⇐⇒
x ∈ L ∩ L′ . 106/127
105/127
K¨ornyezetf¨uggetlen nyelvek z´arts´agi tulajdons´agai
K¨ornyezetf¨uggetlen nyelvek z´arts´agi tulajdons´agai
T´ etel. A determinisztikus cf nyelvek oszt´alya z´ art a komplementer k´epz´esre. Bizony´ıt´ as. (V´ azlat.) ´ ES. ´ Egy adott P = (Q, Σ, Γ, δ, q0 , Z0 , F ) determinisztikus 1. LEP pda-hoz megkonstru´ alunk egy olyan P ′ = (Q ′ , Σ, Γ′ , δ′ , q0′ , Z0′ , F ) determinisztikus pda-t, melyre Lf (P) = Lf (P ′ ) ´es amely soha nem ,,akad el”, mivel minden konfigur´ aci´ oj´ ara van r´ ak¨ovetkez˝ o: minden q ∈ Q ´es Z ∈ Γ eset´en,
Ha egy determinisztikus pda-nak megvan a fenti tulajdons´ aga, m´eg nem biztos, hogy minden input sz´ ot v´egig tud olvasni. Az input olvas´ asa sor´ an ker¨ ulhet ugyanis u ´n. hurok-konfigur´ aci´ oba: (q, ε, A) ⊢ (q1 , ε, α1 ) ⊢ (q2 , ε, α2 ) ⊢ . . . azaz (q, v , A) ⊢ (q1 , v , α1 ) ⊢ (q2 , v , α2 ) ⊢ . . .
(a) vagy minden a ∈ Σ-ra ||δ′ (q, a, Z )|| = 1 ´es δ′ (q, ε, Z ) = ∅, (b) vagy minden a ∈ Σ-ra δ′ (q, a, Z ) = ∅ ´es ||δ′ (q, ε, Z )|| = 1.
107/127
108/127
K¨ornyezetf¨uggetlen nyelvek z´arts´agi tulajdons´agai
K¨ornyezetf¨uggetlen nyelvek z´arts´agi tulajdons´agai
´ ES. ´ A hurok-konfigur´ 2. LEP aci´ ok halmaza megkonstru´ alhat´ o ´es ennek ismret´eben a P = (Q, Σ, Γ, δ, q0 , Z0 , F ) determinisztikus pda atalak´ıthat´o v´egig olvas´ov´ ´ a: minden x ∈ Σ∗ eset´en van olyan q ∈ Q ´ allapot ´es α ∈ Γ∗ sz´ o, hogy ∗ (q0 , x, Z0 ) ⊢ (q, ε, α).
¨ Otlet: Q ′ = Q × {0, 1, 2} ´es P ′ szimul´ alja P-t. Tov´ abb´ a: A ( , 1) ´es ( , 0) alak´ u´ allapotok m´ asodik komponens´eben P ′ azt az inform´ aci´ ot t´ arolja, hogy P volt vagy nem volt v´eg´ allapotban az u´ allapotok lesznek a utols´ o input elolvas´ asa ´ ota. A ( , 2) alak´ v´eg´ allapotok.
´ ES. ´ Egy v´egig olvas´o determinisztikus 3. LEP P = (Q, Σ, Γ, δ, q0 , Z0 , F ) pda-hoz pedig m´ ar tudunk olyan P ′ determinisztikus pda-t konstru´ alni, amely az Lf (P) nyelv komplementer´et ismeri fel.
Ha m´eg nem volt ´es P m´ ar nem v´egezhet t¨obb ε-mozg´ ast, akkor P ′ egy ε-mozg´ assal ´ atv´ alt ( , 0) alak´ u´ allapotb´ ol ( , 2) alak´ u v´eg´ allapotba. K¨ovetkez´esk´eppen, ha ez a sz´ o v´eg´en t¨ort´ent, akkor P ′ elfogadja a sz´ ot. Ha nem a sz´ o v´eg´en t¨ort´ent, akkor a k¨ovetkez˝ o input bet˝ u hat´ as´ ara P ′ visszav´ alt ( , 1) vagy ( , 0) alak´ u´ allapotba att´ ol f¨ ugg˝ oen, hogy P v´eg´ allapotba vagy nem v´eg´ allapotba ´erkezett. Ily m´ odon P ′ ´eppen Lf (P)-t ismeri fel. 109/127
K¨ornyezetf¨uggetlen nyelvek z´arts´agi tulajdons´agai
K¨ornyezetf¨uggetlen nyelvek z´arts´agi tulajdons´agai
Legyen P ′ = (Q ′ , Σ, Γ, δ′ , q0′ , Z0 , F ′ ), ahol
◮
◮ Q′ ◮
F ′ = {(q, 2) | q ∈ Q},
◮
δ′ a k¨ovetkez˝ o:
δ′ a k¨ovetkez˝ o: - minden q ∈ Q, a ∈ Σ ´es Z ∈ Γ-ra, ha δ(q, a, Z ) = (p, γ), akkor ((p, 1), γ) ha p ∈ F δ ′ ((q, 1), a, Z ) = δ ′ ((q, 2), a, Z ) = ((p, 0), γ) ha p 6∈ F
= Q × {0, 1, 2}, (q0 , 0) ha q0 6∈ F ′ q0 = (q0 , 1) ha q0 ∈ F
◮
110/127
- minden q ∈ Q ´es Z ∈ Γ-ra, ha δ(q, ε, Z ) = (p, γ), akkor * δ ′ ((q, 1), ε, Z ) = ((p, 1), γ), ((p, 1), γ) ′ * δ ((q, 0), ε, Z ) = ((p, 0), γ)
ha p ∈ F ha p ∈ 6 F,
- minden q ∈ Q ´es Z ∈ Γ-ra, ha δ(q, ε, Z ) = ∅, akkor legyen δ ′ ((q, 0), ε, Z ) = ((q, 2), Z ).
A fentiek miatt LF (P ′ ) = Lf (P). 111/127
112/127
K¨ornyezetf¨uggetlen nyelvek z´arts´agi tulajdons´agai
K¨ornyezetf¨uggetlen nyelvek z´arts´agi tulajdons´agai ¨ Osszefoglal´ as
K¨ ovetkezm´ eny. Ld ⊂ L2 . (A determinisztikus nyelvek val´odi r´esz´et k´epezik a k¨ornyezetf¨ uggetlen nyelveknek.)
M˝ uvelet
Bizony´ıt´ as. Azt tudjuk, hogy Ld ⊆ L2 . A k´et oszt´ aly nem lehet ugyanaz, mert – mint l´ attuk –, Ld z´ art a komplementer k´epz´esre, L2 pedig nem.
∪ konkaten´ aci´ o ∗
∩ ∩ reg. nyelv komplementer
Bizony´ıt´ as n´elk¨ ul: T´ etel. A determinisztikus cf nyelvek nem z´ artak sem az egyes´ıt´esre, sem a konkaten´ aci´ ora, sem az iter´ aci´ ora.
Z´ arts´ ag cf igen igen igen nem igen nem
Z´ arts´ ag det.cf nem nem nem nem igen igen
114/127
113/127
Eld¨ont´esi k´erd´esek cf nyelvekre
Eld¨ont´esi k´erd´esek cf nyelvekre Eleme-e probl´ema
Ebben a r´eszben a k¨ornyezef¨ uggetlen nyelvek L2 oszt´ aly´ ara vonatkoz´ o eld¨ont´esi k´erd´esekkel foglalkozunk.
Probl´ema: Eld¨onthet˝ o-e tetsz˝ oleges w sz´ o ´es L cf nyelv eset´en, hogy teljes¨ ul-e w ∈ L? T´ etel. Az eleme-e probl´ema cf nyelvekre eld¨ onthet˝ o.
A k¨ornyezef¨ uggetlen nyelveket Chomsky norm´ alalakban l´ev˝ o k¨ornyezef¨ uggetlen nyelvtanokkal reprezent´ aljuk.
Input: Egy w sz´ o ´es egy Chomsky norm´ alform´ aban l´ev˝ o G = (N, Σ, P, S) cf nyelvtannal megadott L cf nyelv (teh´ at L = L(G )). Output: ”Igen” ha w ∈ L, k¨ ul¨onben ”Nem”. Algoritmus: CYK = Cocke-Younger-Kasami algoritmus, melynek l´ep´essz´ ama O(n3 ), ahol n = |w |.
115/127
116/127
Eld¨ont´esi k´erd´esek cf nyelvekre
Eld¨ont´esi k´erd´esek cf nyelvekre
El˝ ok´ esz´ıt´ es: Tfh, |w | = n ≥ 1 ´es legyen wij a w i -edik poz´ıci´oj´ an us´ ag´ u r´esz-szava. kezd˝ od˝ o j hossz´
(CYK) Algoritmus: begin for i := 1 to n do Vi 1 = {A | A → wi 1 ∈ P}; for j := 2 to n do for i := 1 to n − j + 1 do begin Vij = ∅; for k := 1 to j − 1 do Vij = Vij ∪ {A | A → BC ∈ P, B ∈ Vik , C ∈ Vi +k,j−k }; end end
Minden j = 1, . . . , n-re ´es i = 1, . . . , n − j + 1-re meghat´ arozzuk a ∗ Vij = {A ∈ N | A ⇒ wij } halmazt, a k¨ovetkez˝ o elv alapj´ an: j = 1: A ∈ Vi 1 ⇐⇒ A → wi 1 ∈ P. j > 1: A ∈ Vij ⇐⇒ ∃1 ≤ k < j ´es A → BC ∈ P, hogy B ∈ Vik ´es C ∈ Vi +k,j−k . (Dinamikus programoz´ as.) Ezut´ an w ∈ L(G ), akkor ´es csak akkor, ha S ∈ V1n .
Ha S ∈ V1n , akkor a v´ alasz ”Igen”, k¨ ul¨onben ”Nem”.
117/127
Eld¨ont´esi k´erd´esek cf nyelvekre
118/127
Eld¨ont´esi k´erd´esek cf nyelvekre
P´elda. Tekints¨ uk a k¨ovetkez˝ o nyelvtant: P´elda folytat´ asa,
w = abaab.
(1) S → AA (2) S → AS
V11 = {A}
V21 = {S}
V31 = {A}
V41 = {A}
(3) S → b
V12 = {A, S}
V22 = {S}
V32 = {S}
V42 = {A, S}
(4) S → SA
V13 = {A, S}
V23 = {S}
V33 = {A, S}
V14 = {A, S}
V24 = {S}
(5) A → AS (6) A → a
´es legyen w = abaab
V51 = {S}
V15 = {A, S} S ∈ V15 , teh´ at w ∈ L(G ).
(Chomsky norm´ alalakban van ´es nem egy´ertelm˝ u, de ez ut´ obbi most nem ´erdekes.) Sz´ amoljuk ki a Vij halmazokat (j = 1, . . . , 5, i = 1, . . . , 6 − j)!
119/127
120/127
Eld¨ont´esi k´erd´esek cf nyelvekre
Eld¨ont´esi k´erd´esek cf nyelvekre
¨ Uress´ egi probl´ema
Algoritmus: Legyen k a k¨ornyezetf¨ uggetlen nyelvekre vonatkoz´ o pump´ al´ o lemm´ aban (Bar-Hillel lemma) szerepl˝ o sz´ am.
Probl´ema: Eld¨onthet˝ o-e tetsz˝ oleges L cf nyelv eset´en, hogy teljes¨ ul-e L = ∅? T´ etel. Az u ¨ress´egi probl´ema k¨ornyezetf¨ uggetlen nyelvekre eld¨onthet˝ o.
K¨onnyen l´ athat´ o, hogy L 6= ∅ akkor ´es csak akkor, ha van olyan x ∈ L, melyre |x| < k. (Ha |x| ≥ k, akkor alkalmazzuk a pump´ al´ o lemm´ at ´es ”r¨ ovid´ıts¨ uk” x-et.)
alform´ aban l´ev˝ o Input: Egy G = (N, Σ, P, S), Chomsky norm´ nyelvtannal megadott L cf nyelv.
Ez alapj´an egy eld¨ont´esi algoritmus a k¨ovetkez˝ o. Minden olyan x ∈ Σ∗ sz´ ora, melyre |x| < k, k´erdezz¨ uk le, hogy x ∈ L teljes¨ ul-e (az eleme-e probl´ema eld¨onthet˝ o). Ha valamely x-re a v´ alasz ”Igen” (vagyis x ∈ L), akkor a v´ alasz ”Nem”, k¨ ul¨onben ”Igen”.
Output: ”Igen”, ha L = ∅, k¨ ul¨onben ”Nem”.
Az algoritmus termin´ al, mivel csak v´eges sz´ am´ u olyan x sz´ o van, melyre |x| < k.
121/127
Eld¨ont´esi k´erd´esek cf nyelvekre
122/127
Eld¨ont´esi k´erd´esek cf nyelvekre
V´egtelen-e probl´ema
Algoritmus: Legyen k a k¨ornyezetf¨ uggetlen nyelvekre vonatkoz´ o pump´ al´ o lemm´ aban (Bar-Hillel lemma) szerepl˝ o sz´ am.
Probl´ema: Eld¨onthet˝ o-e tetsz˝ oleges L cf nyelv eset´en, hogy L v´egtelen-e? T´ etel. A v´egtelen-e probl´ema k¨ornyezetf¨ uggetlen nyelvekre eld¨onthet˝ o.
K¨onnyen l´ athat´ o, hogy L akkor ´es csak akkor v´egtelen, ha van olyan x ∈ L, melyre k ≤ |x| < 2k. (A bizony´ıt´ as hasonl´ oa regul´ aris nyelvek eset´eben alkalmazott bizony´ıt´ as´ ahoz.)
Input: Egy G = (N, Σ, P, S), Chomsky norm´ alform´ aban l´ev˝ o nyelvtannal megadott L cf nyelv.
Ez alapj´an egy eld¨ont´esi algoritmus a k¨ovetkez˝ o. Minden olyan x ∈ Σ∗ sz´ ora, melyre k ≤ |x| < 2k, k´erdezz¨ uk le, hogy x ∈ L teljes¨ ul-e (az eleme-e probl´ema eld¨onthet˝ o). Ha valamely x-re a v´ alasz ”Igen” (vagyis x ∈ L), akkor a v´ alasz ”Igen”, k¨ ul¨onben ”Nem”.
Output: ”Igen”, ha L v´egtelen, k¨ ul¨onben ”Nem”.
123/127
124/127
Eld¨ont´esi k´erd´esek cf nyelvekre
Eld¨ont´esi k´erd´esek cf nyelvekre ¨ Osszefoglal´ as
Ugyanakkor az ekvivalencia prob´ema k¨ornyezetf¨ uggetlen nyelvek est´en eld¨onthetetlen.
K´ erd´ es Eleme-e ¨ Uress´egi V´egtelen-e Tartalmaz´ as Ekvivalencia
T´ etel. Nem l´etezik olyan algoritmus, amely tetsz˝ oleges L1 , L2 k¨ornyezetf¨ uggetlen nyelvekr˝ol eld¨onti, hogy L1 = L2 teljes¨ ul-e. Bizony´ıt´ as. A k´erd´es visszavezethet˝o a Turing g´epek meg´ all´ asi probl´em´ aj´ ara. K¨ ovetkezm´ eny. Nem l´etezik olyan algoritmus, amely tetsz˝ oleges L1 , L2 k¨ornyezetf¨ uggetlen nyelvekr˝ol eld¨onti, hogy L1 ⊆ L2 teljes¨ ul-e. Bizony´ıt´ as. Ha a tartalmaz´ as eld¨onthet˝ o lenne, akkor az ekvivalencia is eld¨onthet˝ o lenne.
125/127
Eld¨ont´esi k´erd´esek cf nyelvekre Egy megjegyz´es: A k¨ornyezetf¨ uggetlen nyelvekre vonatkoz´ oan m´ ar sz´ amos olyan k´erd´es van, amelynek eld¨ont´es´ere nem l´etezik algoritmus. P´eld´ aul, az el˝ obbiek mellett nem d¨ onthet˝ o el az L = Σ∗ ? L1 ∩ L2 = ∅? k´erd´esek egyike sem. (Ugyanezen k´erd´esek regul´ aris nyelvekre eld¨onthet˝ ok.)
127/127
Eld¨ onthet˝ o-e? igen igen igen nem nem
126/127
