Irodalom Form´ alis nyelvek I. V´ eges automat´ ak ´ es regul´ aris nyelvek
• F¨ ul¨op Zolt´ an, Form´ alis nyelvek ´es szintaktikus elemz´es¨ uk, Polygon, 2004. ´ ´ ´es Iv´ • Esik Zolt´ an, Gomb´ as Eva an Szabolcs: Automat´ ak ´es form´ alis nyelvek p´eldat´ ar, Typotex Kiad´ o, 2011. • J. E. Hopcroft ´es R. Motwani, J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2001 ´es Pearson Education Limited 2014. (A biblia.) • Peter Linz, An Introduction to Formal Languages and Automata, Jones & Barlett Learning, 2012.
F¨ ul¨op Zolt´ an
Aj´ anlott az el˝ oad´ asok l´ atogat´ asa ´es a jegyzetel´es! A vizsg´ an az el˝ oad´ ason elhangzottakat is tudni kell.
SZTE TTK Informatikai Tansz´ekcsoport Sz´ am´ıt´ astudom´ any Alapjai Tansz´ek ´ ad t´er 2. 6720 Szeged, Arp´
2/141
1/141
A form´alis nyelvek egy alkalmaz´asa
A form´alis nyelvek egy alkalmaz´asa
Egy (programoz´ asi) nyelv szintaxisa: azon szab´ alyok ¨ osszess´ege, amelyek meghat´ arozz´ ak a nyelvet.
Aritmetikai kifejez´esek Aritmetikai kifejez´eseknek az A, B ´es C v´ altoz´o jelekb˝ ol, a 0 ´es 1 konstans jelekb˝ ol, a + ´es ∗ m˝ uveleti jelekb˝ ol, valamint a ( ´es ) csoportos´ıt´ o jelekb˝ ol, a
Hogyan, milyen m´ odszerrel adhat´ o meg a programoz´ asi nyelvek szintaxisa?
hkif i htag i hfakti hvalti hkonsti
A legelterjedtebb m´ odszer a generat´ıv nyelvtannal t¨ort´en˝ o szintaxis megad´ as. Adjuk meg az A, B ´es C v´ altoz´okb´ ol, a 0 ´es 1 konstansokb´ ol, a + ´es a ∗ m˝ uveleti jelekb˝ ol, valamint a ( ´es ) z´ ar´ ojelekb˝ ol fel´ep´ıthet˝ o aritmetikai kifejez´esek szintaxis´ at!
→ → → → →
htag i | hkif i + htag i hfakti | htag i ∗ hfakti (hkif i) | hvalti | hkonsti A|B |C 0|1
szab´ alyok alkalmaz´ as´ aval fel´ep´ıthet˝ o jelsorozatokat (szavakat) nevezz¨ uk. A | jel v´ alaszt´ asi lehet˝ os´eget jelent, olvassuk ”vagy”-nak. Ez egy generat´ıv nyelvtan.
Ilyenek p´eld´ aul az A, 1, A + 1, A + B, A ∗ (B + 1) aritmetikai kifejez´esek. Az ¨ osszes ilyen kifejez´es egy nyelvet alkot.
3/141
4/141
A form´alis nyelvek egy alkalmaz´asa
A form´alis nyelvek egy alkalmaz´asa
Levezet´es:
Levezet´es:
hkif i
⇒
hfakti ∗ (hfakti + hfakti)
htag i htag i ∗ hfakti
⇒ ⇒
hvalti ∗ (hfakti + hfakti) hvalti ∗ (hvalti + hfakti)
⇒ ⇒
htag i ∗ (htag i + htag i) hfakti ∗ (htag i + htag i)
⇒ ⇒
A ∗ (B + hkonsti) A ∗ (B + 1)
⇒
hfakti ∗ (hfakti + hfakti)
⇒ ⇒
⇒ ⇒
⇒
htag i ∗ (hkif i) htag i ∗ (hkif i + htag i)
⇒ ⇒
hfakti ∗ (hfakti + htag i)
hvalti ∗ (hvalti + hkonsti) A ∗ (hvalti + hkonsti)
Jel¨ ol´es: hkif i ⇒∗ A ∗ (B + 1)
Minden l´ep´esben az al´ ah´ uzott szintaktikai egys´eget helyettes´ıtj¨ uk a megfelel˝o szab´ aly jobb oldal´ an ´ all´o valamelyik kifejez´essel.
6/141
5/141
A form´alis nyelvek egy alkalmaz´asa
A form´alis nyelvek egy alkalmaz´asa Egy m´ asik p´elda: a FONYA programoz´ asi nyelv szintaxisa:
Az A, B, C , 0, 1, +, ∗, ( ´es ) jelekb˝ ol ´ all´o aritmetikai kifejez´es szintaxisa: egy jelsorozat (vagy sz´ o) akkor ´es csak akkor aritmetikai kifejez´es, ha a hkif i-b˝ ol a fenti szintaktikai szab´ alyok alkalmaz´ as´ aval t¨ ort´en˝ o levezet´essel megkaphat´ o. R¨oviden: w sz´ o aritmetikai kifejez´es ⇐⇒ hkif i ⇒∗ w .
7/141
hprogrami hut.listai huti
→ → →
hert.adoi hifuti hwhileuti hblokki hrelacioi hrelaciojel i
→ → → → → →
hut.listai. huti | huti; hut.listai hert.adoi | hifuti | hwhileuti | hblokki hvalti := hkif i if hrelacioi then huti else huti while hrelacioi do huti begin hut.listai end hkif i hrelaciojel i hkif i < | > | = | 6=
8/141
A form´alis nyelvek egy alkalmaz´asa
A form´alis nyelvek egy alkalmaz´asa
Egy m´ asik p´elda: a FONYA programoz´asi nyelv szintaxisa: hkif i htag i hfakti hvalti hkonsti
→ → → → →
Egy w jelsorozat akkor ´es csakis akkor szintaktikusan helyes FONYA nyelv˝ u program, ha hprogrami ⇒∗ w .
htag i | hkif i + htag i hfakti | htag i ∗ hfakti (hkif i) | hvalti | hkonsti A|B |C 0|1
Ilyen p´eld´ aul a bal oldali jelsorozat ´es nem ilyen a jobb oldali: A := 0; while A < C do begin A := A + 1; B := B ∗ C end; C := C ∗ B.
A := 0; while A + C do begin A := A + 1 B := B ∗ C end; C := C ∗ B.
A jobb oldaliban k´et szintaktikus hiba van!
9/141
10/141
´ anos fogalmak, jel¨ol´esek Altal´
A form´alis nyelvek egy alkalmaz´asa Az elemz´es alapk´erd´ese:
´ ec´e: szimb´ Ab´ olumoknak egy tetsz˝ oleges v´eges, nem¨ ures halmaza. ´ Altal´ aban Σ-val jel¨ olj¨ uk.
Amennyiben adott egy programoz´ asi nyelv szintaxisa ´es adott egy – ezen a nyelven ´ırott – program, akkor hogyan tudjuk eld¨onteni azt, hogy az adott program engedelmeskedik-e a szintaxisnak, vagyis szintaktikusan helyes-e?
Σ´ ab´ec´e feletti sz´ o: egy a1 . . . ak alak´ u sorozat, ahol k ≥ 0 ´es a1 , . . . , ak ∈ Σ.
R¨oviden: igaz-e, hogy hprogrami ⇒∗ w ?
k = 0 eset: u ¨res sz´ onak nevezz¨ uk, jele λ.
T¨ obb algoritmus is l´etezik, l´ asd a ”Szintaktikus elemz´esi m´ odszerek” c. kurzus anyag´ at.
P´elda ´ ab´ec´ere ´es szavakra: Σ = {a, b}, λ, a, b, aba, aababba, stb. Programoz´ asban: ASCII, Unicode ´ ab´ec´ek, BEGIN, END, IF, ALMA, K1, tov´ abbi kulcsszavak, azonos´ıt´ ok, 123, -412.2, K1+123, egy´eb sz´ amok, kifejez´esek stb pedig szavak.
11/141
12/141
´ anos fogalmak, jel¨ol´esek Altal´
´ anos fogalmak, jel¨ol´esek Altal´
¨ Osszes szavak halmaza: Ha w = xy , akkor x a w prefixe, y a w suffixe.
Σ∗ = {a1 . . . ak | k ≥ 0, a1 , . . . , ak ∈ Σ}
Σ+ = {a1 . . . ak | k ≥ 1, a1 , . . . , ak ∈ Σ} = Σ∗ − {λ}
P´elda: abb pefixei λ, a, ab, abb, suffixei abb, bb, b, λ
P´elda: Σ∗ = {λ, a, b, aa, ab, ba, bb, aaa, . . .}, Σ+ = {a, b, aa, ab, ba, bb, aaa, . . .}
Egy w sz´ o hossz´ an a benne el˝ ofordul´ o bet˝ uk multiplicit´ assal vett sz´ am´ at ´ertj¨ uk. A jele |w |, a pontos defin´ıci´o a k¨ovetkez˝ o: (i) ha w = λ, akkor |w | = 0,
Konkaten´ aci´ o: az u, v ∈ Σ∗ szavak egym´as ut´ an ´ır´ as´ aval kapott ∗ uv ∈ Σ sz´ o. P´elda: ha u = abb, v = ba, akkor uv = abbba, uλ = λu = u. A konkaten´ aci´ o asszociat´ıv: u(vw ) = (uv )w minden ∗ u, v , w ∈ Σ -ra n z }| { Hatv´ anyoz´ as: u n = uu . . . u, u 0 = λ, u = abb-re u 3 = abbabbabb.
(ii) ha w = av , valamely a ∈ Σ ´es v ∈ Σ∗ -ra, akkor |w | = 1 + |v |. P´elda: |λ| = 0, |a| = 1, |ab| = 2, |abb| = 3.
14/141
13/141
´ anos fogalmak, jel¨ol´esek Altal´
M˝uveletek nyelvekkel Legyenek L, L1 , L2 ⊆ Σ∗ nyelvek. Az
Nyelv: Σ∗ tetsz˝ oleges r´eszhalmaz´ at Σ feletti nyelvnek nevezz¨ uk.
L1 ∪ L2 , L1 ∩ L2 ´es L1 − L2
P´elda {a, b} feletti nyelvekre: ◮
{aa, bab, abba} (v´eges nyelv),
◮
{w ∈ Σ∗ | |w | p´ aros },
◮
az ismert halmazelm´eleti m˝ uveletek. Tov´ abb´ a ◮
{λ, ab, aabb, aaabbb, . . .} = {an b n | n ≥ 0}.
◮
L = Σ∗ − L az L komplementere,
L1 L2 = {uv | u ∈ L1 , v ∈ L2 } az L1 ´es L2 konkaten´ aci´ oja, ol ´es L2 -b˝ ol Minden lehets´eges m´ odon v´ alasztunk L1 -b˝ szavakat ´es ”¨ osszel´ ancoljuk” (konkaten´ aljuk) ˝ oket:
A m´ ar ismert aritmetikai kifejez´esek halmaza egy nyelv az {A, B, C , 0, 1, +, ∗, (, )} ´ ab´ec´e felett.
{λ, ab, bab}{b, ba} = {b, ba, abb, abba, babb, babba}
Az ¨ osszes Σ feletti nyelvek halmaza: P(Σ∗ ) (kontinuum sz´ amoss´ ag´ u).
Σ∗ {aba} = {waba | w ∈ Σ∗ }, az aba-ra v´egz˝ od˝ o szavak halmaza. 15/141
16/141
M˝uveletek nyelvekkel
M˝uveletek nyelvekkel
A nyelvek konkaten´ aci´ oja is asszociat´ıv: Megjegyz´es: ∅∗ = {λ} ´es minden L nyelvre λ ∈ L∗ .
L1 (L2 L3 ) = (L1 L2 )L3 ,
Tov´abb´ a: L∗ = {λ} ∪ L+ .
ez´ert a z´ ar´ ojelez´es elhagyhat´o. n
Ln
Az ∪, ∩ ´es komplementer m˝ uveleteket Boole m˝ uveleteknek, az ∪, konkaten´ aci´ o ´es iter´ aci´ o m˝ uveleteket pedig regul´ aris m˝ uveleteknek nevezz¨ uk.
z }| { = LL . . . L, L0 = {λ}
◮
Hatv´ anyoz´ as:
◮
L∗ = {λ} ∪ L ∪ LL ∪ LLL ∪ . . . az L iter´ altja, Tetsz˝oleges sz´ am´ u (0 is megengedett) L-beli sz´ o konkaten´aci´ ojak´ent megkaphat´ o szavak halmaza. {ab, ba}∗ = {λ, ab, ba, abab, abba, baab, baba, ababab, . . .}
◮
L+ = L ∪ LL ∪ LLL ∪ . . . (a 0 eset kiz´ arva). 17/141
M˝uveletek nyelvekkel
18/141
Generat´ıv nyelvtanok
N´eh´ any, nyelv m˝ uveletekre vonatkoz´ o azonoss´ ag: L1 ∪ (L2 ∪ L3 ) = (L1 ∪ L2 ) ∪ L3
L1 (L2 L3 ) = (L1 L2 )L3
L1 ∪ L2 = L2 ∪ L1
L{λ} = {λ}L = L
Egy olyan, k¨onnyen le´ırhat´ o eszk¨ozzel ismerked¨ unk meg, amely alkalmas (´ altal´ aban v´egtelen) nyelvek megad´ as´ ara. Az eszk¨oz neve generat´ıv nyelvtan (vagy generat´ıv grammatika).
L∪L =L L∪∅ = ∅∪L = L
Tov´ abb´ a:
M´ as sz´ oval: a generat´ıv nyelvtanok olyan v´egesen specifik´ alhat´ o eszk¨oz¨ ok, melyekkel nyelveket tudunk reprezent´ alni.
L∅ = ∅L = ∅ L1 (L2 ∪ L3 ) = L1 L2 ∪ L1 L3 (L1 ∪ L2 )L3 = L1 L3 ∪ L2 L3 (L1 ∪ L2 )∗ = (L∗1 L2 )∗ L∗1
(L1 L2 )∗ = {λ} ∪ L1 (L2 L1 )∗ L2
19/141
20/141
Generat´ıv nyelvtanok
Generat´ıv nyelvtanok
Generat´ıv nyelvtan: egy G = (N, Σ, P, S) n´egyes, ahol: P´elda: ◮
N egy ´ ab´ec´e, a nemtermin´ alis ´ ab´ec´e,
◮
Σ egy ´ ab´ec´e, a termin´ alis (befejez˝ o, v´egs˝ o) ´ ab´ec´e, amire N ∩ Σ = ∅,
◮ ◮
G1 = ({S, A}, {a, b}, {S → aAb, aA → aaAb, A → λ}, S) egy nyelvtan, ahol
S ∈ N a kezd˝ o szimb´ olum (vagy start szimb´ olum),
◮
P pedig α → β alak´ uu ´n. ´ at´ır´ asi szab´ alyok v´eges halmaza, ∗ ahol α, β ∈ (N ∪ Σ) ´es α-ban van legal´ abb egy nemtermin´ alis bet˝ u.
◮
(α a szab´ aly bal oldala, β a jobb oldala.)
{S, A} a nemtermin´ alis ´ ab´ec´e, {a, b} a termin´ alis ´ ab´ec´e,
◮
S a kezd˝ o (start) szimb´ olum,
◮
{S → aAb, aA → aaAb, A → λ} a szab´ alyok halmaza.
aA → aaAb egy szab´ aly, aminek a bal oldala aA, a jobb oldala pedig aaAb
22/141
21/141
Generat´ıv nyelvtanok
Generat´ıv nyelvtanok
K¨ozvetlen levezet´es (deriv´ aci´ o): P´elda: tetsz˝ oleges γ, δ ∈ (N ∪ Σ)∗ eset´en γ ⇒G δ, ha van olyan α → β ∈ P szab´ aly ´es vannak olyan α′ , β ′ ∈ (N ∪ Σ)∗ szavak, amelyekre fenn´ allnak, hogy γ = α′ αβ ′ , δ = α′ ββ ′ .
G1 = ({S, A}, {a, b}, {S → aAb, aA → aaAb, A → λ}, S) baAAa ⇒ baaAbAa az aA → aaAb szab´ allyal baaAbAa ⇒ baaAba az A → λ szab´ allyal
α′
α γ
β′
⇒G
α′
β
β′
δ
23/141
24/141
Generat´ıv nyelvtanok
Generat´ıv nyelvtanok
Levezet´esek:
P´elda:
γ ⇒G δ: egy l´ep´es
G1 = ({S, A}, {a, b}, {S → aAb, aA → aaAb, A → λ}, S) S
γ ⇒nG δ: n ≥ 0 l´ep´es (γ ⇒0G δ ⇐⇒ γ = δ) γ ⇒+ abb egy l´ep´es G δ: legal´
⇒ ⇒
aAb aaaAbbb
⇒ ⇒
aaAbb aaabbb
Teh´ at: S ⇒∗ aaabbb, S ⇒+ aaabbb, S ⇒4 aaabbb mind teljes¨ ulnek.
γ ⇒∗G δ: valamennyi (esetleg 0) l´ep´es
Tov´ abb´ a: aAb ⇒ aaAbb, aAb ⇒2 aaaAbbb, teh´ at aAb ⇒∗ aaAbb, ∗ aAb ⇒ aaaAbbb.
Ha nem okoz f´elre´ert´est, ⇒G helyett ⇒-t ´ırunk.
Legink´ abb azok a levezet´esek ´erdekelnek benn¨ unket, amelyek a kezd˝ o szimb´ olumb´ol indulnak ki ´es termin´ alis sz´ oban v´egz˝ odnek.
25/141
Generat´ıv nyelvtanok
26/141
Generat´ıv nyelvtan P´elda:
G = (N, Σ, P, S) nyelvtan ´ altal gener´ alt nyelv: Az el˝ obbi G1 nyelvtan ekvivalens a L(G ) = {u ∈ Σ∗ | S ⇒∗G u}.
G2 = ({S}, {a, b}, {S → aSb, S → ab}, S)
A G1 = ({S, A}, {a, b}, {S → aAb, aA → aaAb, A → λ}, S) p´eld´ aban L(G1 ) = {an b n | n ≥ 1}.
nyelvtannal, mert ugyancsak L(G2 ) = {an b n | n ≥ 1}.
Egy nyelvet ´ altal´ aban nem csak egy nyelvtannal lehet gener´ alni: a ′ ′ ′ ′ ′ G = (N, Σ, P, S) ´es G = (N , Σ , P , S ) nyelvtanok ekvivalensek, ha L(G ) = L(G ′ ).
27/141
28/141
Generat´ıv nyelvtanok
Generat´ıv nyelvtan Az A → α1 , . . . , A → αn szab´ alyok fel´ır´ as´ at a k¨ovetkez˝ ok´eppen r¨ ovid´ıtj¨ uk: A → α1 | . . . | αn .
P´elda: Gar = (N, Σ, P, S), ahol ◮ ◮ ◮ ◮
N = {K , T , F } ,
P´eld´ aul, a Gar nyelvtan szab´ alyai megadhat´ ok ´ıgy is:
Σ = {+, ∗, (, ), a} ,
- K → K + T | T,
S = K, P ={
- T → T ∗ F | F, - F → (K ) | a.
- K → K + T, K → T, - T → T ∗ F, T → F, - F → (K ), F → a}.
Egy levezet´es Gar -ban:
Ekkor L(Gar ) az a-b´ ol valamint a (, ), + ´es ∗ jelekb˝ ol k´epezhet˝ o aritmetikai kifejez´esek halmaza.
K ⇒ T ⇒ T ∗ F ⇒ F ∗ F ⇒ (K ) ∗ F ⇒ (K + T ) ∗ F ⇒∗ (F + F ) ∗ F ⇒∗ (a + a) ∗ a
30/141
29/141
´ anos jel¨ol´esek Altal´
Chomsky nyelvoszt´alyok A G = (N, Σ, P, S) nyelvtan
◮
Az a, b, c, d, . . . szimb´ olumok Σ elemeit,
◮
az A, B, C , D, . . ., ´es S szimb´ olumok N elemeit,
◮
0 t´ıpus´ u (vagy ´ altal´ anos), ha r´ a semmilyen korl´ atoz´ as nincs.
◮
az . . . , U, V , W , X , Y , Z szimb´ olumok N ∪ Σ elemeit,
◮
1 t´ıpus´ u (vagy k¨ornyezetf¨ ugg˝ o), ha P-ben minden szab´ aly αAβ → αδβ alak´ u, ahol δ 6= λ. Kiv´etel, az S → λ szab´ aly, aly jobb ekkor azonban az S nem szerepelhet semelyik szab´ oldal´ an.
◮
2 t´ıpus´ u (vagy k¨ornyezetf¨ uggetlen), ha P-ben minden szab´ aly A → α alak´ u.
◮ ◮
az α, β, γ, δ, . . . szimb´ olumok (N ∪
Σ)∗
elemeit,
´es az . . . , u, v , w , x, y , z szimb´ olumok Σ∗ elemeit
fogj´ ak jel¨ olni. ◮
31/141
3 t´ıpus´ u (vagy regul´ aris), ha P-ben minden szab´ aly A → xB vagy A → x alak´ u.
32/141
Chomsky nyelvoszt´alyok
Chomsky nyelvoszt´alyok
Egy adott G nyelvtan eset´en a legnagyobb olyan i ∈ {0, 1, 2, 3} az u. ´erdekes, melyre a nyelvtan i t´ıpus´
Az i ∈ {0, 1, 2, 3} t´ıpus´ u nyelvek oszt´ aly´ at Li -vel jel¨ olj¨ uk. Az nyilv´anval´o, hogy L3 ⊆ L2 ´es L1 ⊆ L0 , mert minden 3-t´ıpus´ u nyelvtan 2-t´ıpus´ u is ´es minden 1-t´ıpus´ u nyelvtan 0-t´ıpus´ u is.
Pl. a G1 , G2 ´es Gar nyelvtanok rendre 1, 2 ´es 2 t´ıpus´ uak. Egy adott L ⊆ Σ∗ nyelvet i t´ıpus´ unak mondunk valamely i ∈ {0, 1, 2, 3}-re, ha van olyan i t´ıpus´ u G nyelvtan, amelyre L = L(G ). Itt is a legnagyobb olyan i az ´erdekes, melyre a nyelv i t´ıpus´ u.
K´es˝ obb l´ atni fogjuk, hogy ´erv´enyes a Chomsky nyelvhierarchia: L3 ⊆ L2 ⊆ L1 ⊆ L0 , s˝ ot az er˝ osebb L3 ⊂ L2 ⊂ L1 ⊂ L0
Pl. az L(G1 ), L(G2 ) ´es L(Gar ) nyelvek mindegyike 2 t´ıpus´ u ´es be lehet bizony´ıtani, hogy egyik sem 3 t´ıpus´ u.
alakja is.
33/141
Chomsky nyelvoszt´alyok
V´eges automat´ak, regul´aris kifejez´esek ¨ Osszefoglal´ as
0
Tov´abbi program: El˝ osz¨ or a regul´ aris nyelveket (vagyis a regul´ aris nyelvtanokkal gener´ alhat´ o nyelveket) vizsg´ aljuk.
0 1
1 2
Bevezet¨ unk tov´ abbi k´et olyan eszk¨ozt, amelyekkel regul´ aris nyelveket lehet megadni (reprezent´ alni): a v´eges automat´ akat ´es a regul´ aris kifejez´eseket.
2 3
Nyelvtanok
34/141
3
Megmutatjuk, hogy mind a v´eges automat´ akkal felismerhet˝ o nyelvek, mind a regul´ aris kifejez´esekkel reprezent´ alhat´ o nyelvek megegyeznek a regul´ aris nyelvekkel.
Nyelvek
A bal oldali az eddigiek alapj´ an vil´ agos, a jobb oldalit fokozatosan, teljesen a f´el´ev v´eg´ere l´ atjuk be. 35/141
36/141
V´eges automat´ak
V´eges automat´ak
Az M = (Q, Σ, δ, q0 , F ) rendszert determinisztikus automat´ anak nevezz¨ uk, ahol:
Automata megad´ asa ir´ any´ıtott gr´ afk´ent: Az ´ allapotok a gr´ af cs´ ucsai,
1. Q egy nem u ¨res, v´eges halmaz, az ´ allapotok halmaza,
ha δ(q, a) = p, akkor a q cs´ ucsb´ol egy ´elet ir´ any´ıtunk a p cs´ ucsba ´es az ´elet ell´ atjuk az a c´ımk´evel,
2. Σ egy ´ ab´ec´e, az input ´ ab´ec´e, 3. q0 ∈ Q a kezd˝ o´ allapot,
4. F ⊆ Q a v´eg´ allapotok halmaza,
a
5. δ : Q × Σ → Q egy lek´epez´es, az ´ atmenetf¨ uggv´eny.
q
p
´es azt mondjuk, hogy az automata a q ´ allapotb´ ol az a input allapotba. szimb´ olum hat´ as´ ara ´ atmegy a p ´ A kezd˝ o ´es a v´eg´ allapotokat reprezent´ al´ o cs´ ucsokat megjel¨ olj¨ uk.
37/141
V´eges automat´ak
V´eges automat´ak
P´elda: M3 = (Q, Σ, δ, q0 , F ) egy automata, ahol ◮ ◮ ◮
38/141
Az M3 automata megad´ asa ir´ any´ıtott gr´ afk´ent:
Q = {q0 , q1 , q2 },
kezd˝o a´llapot: q0 v´eg´allapot-halmaz: {q0}
Σ = {a, b},
F = {q0 }, tov´ abb´ a
b
q1 a
◮ ◮ ◮
δ(q0 , a) = q1 , δ(q0 , b) = q0 , δ(q1 , a) = q2 , δ(q1 , b) = q1 , δ(q2 , a) = q0 , δ(q2 , b) = q2 .
b
a
q0 a q2
b 39/141
40/141
V´eges automat´ak
V´eges automat´ak M konfigur´ aci´ oinak halmaza: C = Q × Σ∗ .
Automata megadhat´ o t´ abl´ azat form´ aban is. A kezd˝ o´ allapotot a t´ abl´ azat els˝ o sor´ aba ´ırjuk, a v´eg´ allapotokat pedig megjel¨ olj¨ uk.
A (q, a1 . . . an ) konfigur´ aci´ o azt jelenti, hogy M a q ´ allapotban van ´es az a1 . . . an sz´ ot kapja inputk´ent.
Az M3 automata megad´ asa t´ abl´ azattal: δ
a
b
⋆q0
q1
q0
q1
q2
q1
q2
q0
q2
´ Atmeneti rel´ aci´ o: (q, w ), (q ′ , w ′ ) ∈ C eset´en (q, w ) ⊢M (q ′ , w ′ ) ha w = aw ′ , valamely a ∈ Σ-ra ´es δ(q, a) = q ′ . (q, w ) ⊢M (q ′ , w ′ ), egy l´ep´es
(q, w ) ⊢nM (q ′ , w ′ ), n ≥ 0 l´ep´es
′ ′ (q, w ) ⊢+ abb egy l´ep´es M (q , w ), legal´
(q, w ) ⊢∗M (q ′ , w ′ ), valamennyi (esetleg 0) l´ep´es
41/141
V´eges automat´ak
42/141
V´eges automat´ak ´ Atmenetek az M3 automat´ aban:
Az M = (Q, Σ, δ, q0 , F ) automata ´ altal felismert nyelven az L(M) = {w ∈ Σ∗ | (q0 , w ) ⊢∗M (q, λ) ´es q ∈ F }
kezd˝o a´llapot: q0 v´eg´allapot-halmaz: {q0}
nyelvet ´ertj¨ uk.
b
q1
ol a w hat´ as´ ara valamelyik q ∈ F v´eg´ allapotba Szavakkal: q0 -b´ jutunk.
a b
a
q0
M a q2
w
b
q0
F
w ∈ L(M) 43/141
(q1 , babb) ⊢M3 (q2 , abb) ⊢M3 (q0 , bb) ⊢2M3 (q0 , λ), (q0 , babaa) ⊢M3 (q0 , abaa) ⊢M3 (q1 , baa) ⊢M3 (q1 , aa) ⊢M3 (q2 , a) ⊢M3 (q0 , λ) ´es (q0 , abb) ⊢M3 (q1 , bb) ⊢M3 (q1 , b) ⊢M3 (q1 , λ)
44/141
V´eges automat´ak
V´eges automat´ak
Az M3 automata ´ altal felismert L(M3 ) nyelv azon szavakb´ ol ´ all, uk sz´ ama oszthat´ o h´ arommal. amelyekben az a bet˝ kezd˝o a´llapot: q0 v´eg´allapot-halmaz: {q0}
A determinisztikus automata ´ altal´ anos´ıt´ asa: nemdeterminisztikus automata. Az M = (Q, Σ, δ, q0 , F ) rendszert nemdeterminisztikus automat´anak nevezz¨ uk, ahol:
b
q1 a b
1. Q egy nem u ¨res, v´eges halmaz, az ´ allapotok halmaza,
a
q0
2. Σ egy ´ ab´ec´e, az input ´ ab´ec´e,
a
3. q0 ∈ Q a kezd˝ o´ allapot,
q2
4. F ⊆ Q a v´eg´ allapotok halmaza,
b
5. δ : Q × Σ → P(Q) egy lek´epez´es, az ´ atmenetf¨ uggv´eny. Egy input szimb´ olum hat´ as´ ara egy ´ allapotb´ ol t¨obb ´ allapotba is atmehet. Az ´ ´ altal´ anos´ıt´ as val´oj´ aban nem n¨ oveli meg a felismer˝ o kapacit´ ast.
babaa ∈ L(M3 ), mert: (q0 , babaa) ⊢M3 (q0 , abaa) ⊢M3 (q1 , baa) ⊢M3 (q1 , aa) ⊢M3 (q2 , a) ⊢M3 (q0 , λ) abb 6∈ L(M3 ), mert: (q0 , abb) ⊢M3 (q1 , bb) ⊢M3 (q1 , b) ⊢M3 (q1 , λ)
45/141
V´eges automat´ak
46/141
V´eges automat´ak
A nemdeterminisztikus automata egy input szimb´ olum hat´ as´ ara egy ´ allapotb´ ol t¨obb ´ allapotba is ´ atmehet:
P´elda: Maba = (Q, Σ, δ, q0 , F ) egy nemdeterminisztikus automata, ahol ◮
δ(q, a) = {q1, . . . , qn }
◮
q1 a q
a a
◮
q2
Q = {q0 , q1 , q2 , q3 }, Σ = {a, b}, F = {q3 }, tov´ abb´ a ◮ ◮
..
◮ ◮
qn
δ(q0 , a) = {q0 , q1 }, δ(q0 , b) = {q0 }, δ(q1 , a) = ∅, δ(q1 , b) = {q2 }, δ(q2 , a) = {q3 }, δ(q2 , b) = ∅, δ(q3 , a) = δ(q3 , b) = {q3 }. a, b
Az is megengedett, hogy δ(q, a) = ∅.
a, b
a q0
47/141
b q1
a q2
q3
48/141
V´eges automat´ak
V´eges automat´ak Az ´ atmeneti rel´ aci´ o ´es a felismert nyelv nemdeterminisztikus automat´akra:
Az Maba automata megad´ asa t´ abl´ azattal: δ
a
b
q0
q0 , q1
q0
q1
´ Atmeneti rel´ aci´ o: (q, w ), (q ′ , w ′ ) ∈ C eset´en (q, w ) ⊢M (q ′ , w ′ ) ha w = aw ′ , valamely a ∈ Σ-ra ´es q ′ ∈ δ(q, a).
q2
q2
q3
⋆q3
q3
Az M = (Q, Σ, δ, q0 , F ) automata ´ altal felismert nyelven az L(M) = {w ∈ Σ∗ | (q0 , w ) ⊢∗M (q, λ) valamely q ∈ F -re}
q3
nyelvet ´ertj¨ uk. ol a w hat´ as´ ara el´erhet˝ o valamely q ∈ F v´eg´ allapot Szavakkal: q0 -b´ (ugyanakkor esetleg nem v´eg´ allapotok is el´erhet˝ ok).
49/141
V´eges automat´ak
50/141
V´eges automat´ak
a, b
a, b
a q0
b q1
Lehetnek olyan szavak, amelyeket egy nemdeterminisztikus automata nem tud v´egig olvasni, mert a δ(q, a) = ∅ alak´ u atmenetek miatt ”elakadhat”. A teljesen defini´ ´ alt automat´ ak viszont minden sz´ ot v´egig tudnak olvasni.
a q2
q3
Az M = (Q, Σ, δ, q0 , F ) nemdeterminisztikus automata teljesen defini´ alt (vagy: teljes), ha minden q ∈ Q ´es a ∈ Σ eset´en δ(q, a) legal´ abb egy elem˝ u.
L(Maba ) = {uabav | u, v ∈ Σ∗ }, teh´ at Maba pontosan azon Σ∗ -beli o. szavakat ismeri fel amelyekben el˝ ofordul az aba r´esz-sz´
A determinisztikus automat´ ak teljesen defini´ altak. Tov´ abb´ a, minden nemdeterminisztikus automata k¨onnyen teljess´e tehet˝o egy u ´n. ”csapda” ´ allapot bevezet´es´evel, an´elk¨ ul, hogy a felismert nyelv megv´ altozna.
Maba nemdeterminisztikus!
51/141
52/141
V´eges automat´ak
V´eges automat´ak
T´ etel. Tetsz˝oleges M = (Q, Σ, δ, q0 , F ) nemdeterminisztikus automat´ ahoz megadhat´ o olyan M ′ = (Q ′ , Σ, δ′ , q0 , F ) teljesen defini´ alt automata, melyre L(M) = L(M ′ ).
P´elda. Az Maba automata teljess´e t´etele. a, b
Bizony´ıt´ as. Ha M teljesen defini´ alt, akkor legyen M ′ = M. ′ K¨ ul¨onben, legyen Q = Q ∪ {qc }, ahol qc 6∈ Q, vagyis egy u ´j allapot (a ”csapda” ´ ´ allapot). Tov´ abb´ a, minden q ∈ Q ´es a ∈ Σ eset´en, legyen δ(q, a) ha δ(q, a) 6= ∅ ′ δ (q, a) = {qc } ha δ(q, a) = ∅.
q0
a, b
a
b
q1
a
q2
a
q3
b qc
a, b
V´eg¨ ul, minden a ∈ Σ-ra, legyen δ′ (qc , a) = {qc }.
53/141
V´eges automat´ak
54/141
V´eges automat´ak M ′ = (Q ′ , Σ, δ′ , q0′ , F ′ ), ahol
T´ etel. Egy nyelv akkor ´es csak akkor ismerhet˝ o fel nemdeterminisztikus automat´ aval, ha felismerhet˝ o determinisztikus automat´ aval.
◮ ◮ ◮
Bizony´ıt´ as. a) Ha egy nyelv felismerhet˝ o determinisztikus automat´ aval akkor felismerhet˝ o nemdeterminisztikus automat´ aval is.
◮
Q ′ = P(Q) (= {S | S ⊆ Q}), a hatv´ anyhalmaz, ′ q0 = {q0 }, F ′ = {S ⊆ Q | S ∩ F 6= ∅}, δ′ : Q ′ × Σ → Q ′ az a lek´ oleges S ∈ Q ′ ´es Sepez´es amelyre tetsz˝ ′ a ∈ Σ eset´en δ (S, a) = q∈S δ(q, a).
b) Ford´ıtva: legyen M = (Q, Σ, δ, q0 , F ) egy nemdeterminisztikus automata. Megadunk egy M ′ = (Q ′ , Σ, δ′ , q0′ , F ′ ) determinisztikus automat´ at, amelyre L(M ′ ) = L(M).
a a a a a a
A konstrukci´ o neve: hatv´ anyhalmaz konstrukci´ o.
a
S
55/141
δ ′ (S, a) =
S
q∈S
δ(q, a)
56/141
V´eges automat´ak
V´eges automat´ak
M′ ´ allapotai az M ´ allapotaib´ ol k´epzett halmazok. Nyilv´ anval´o, asa: hogy M ′ determinisztikus. Az L(M ′ ) = L(M) bizony´ıt´
Az M ´es M ′ felismeri w = a1 . . . ak sz´ ot. a1
´ ıt´ All´ as. Minden w ∈ Σ∗ -ra ´es S ⊆ Q-ra
a2
ak−1
ak
({q0 }, w ) ⊢∗M ′ (S, λ) akkor ´es csak akkor, ha
S = {q ∈ Q | (q0 , w ) ⊢∗M (q, λ)}.
Szavakkal: Az M-ben a w hat´ as´ ara el´erhet˝ o´ allapotok halmaza megegyezik azzal az ´ allapottal, melybe M ′ a w hat´ as´ ara jut. Az oval. all´ıt´ ´ as k¨onnyen igazolhat´ o |w | szerinti indukci´
q0
q1
S0
S1
... qk−1
qk (∈ F )
Sk−1
Sk (∩F 6= ∅)
Az ´ all´ıt´ asb´ ol azonnal k¨ovetkezik, hogy L(M ′ ) = L(M), mert mindk´et automata akkor ismeri fel w -t, ha S-ben van legal´ abb egy F -beli ´ allapot.
58/141
57/141
V´eges automat´ak
V´eges automat´ak
Egy fontos megjegyz´es:
P´elda. Determiniz´ aljuk az Maba nemdeterminisztikus automat´ at! a, b
A hatv´ anyhalmaz konstrukci´ oval kapott determinisztikus automata allapotainak a sz´ ´ ama exponenci´ alisan n¨ ovekedhet az eredeti ol 2n -re). nemdeterminisztikus automata ´ allapotaihoz k´epest (n-r˝ Ez nagy ´ allapotsz´ am´ u rendszerek eset´en ´ allapott´er robban´ ast eredm´enyez.
a, b
a q0
Szerencs´ere a helyzet ´ altal´ aban enn´el sokkal jobb. A gyakorlatban u ´gy j´ arunk el, hogy a determinisztikus automata {q0 } kezd˝ o´ allapot´ ab´ ol kiindulva csak azokat az ´ allapotokat konstru´ aljuk meg, amelyek ezen kezd˝ o´ allapotb´ ol el´erhet˝ ok. Ez a tr¨ ukk ´ altal´ aban n a 2 -n´el j´oval kevesebb ´ allapotot eredm´enyez. (L´ asd a k¨ovetkez˝ o p´eld´ at.)
b q1
a q2
q3
L(Maba ) = {uabav | u, v ∈ Σ∗ }
59/141
60/141
V´eges automat´ak
V´eges automat´ak
´ P´elda. Atmenetek a {q0 , q1 } ´ allapotb´ ol:
P´elda. Az Maba automata determiniz´ al´ asa: b
a
q0
b q0 , q1
q0 , q2
b
a
a
b
q0 q1 b
b q0 q2
b
q0 q2 q3
q0 q3
a a
a
q0 q1 q3
a A kapott automata determinisztikus ´es 6 ´ allapota van (16 helyett). 61/141
V´eges automat´ak
V´eges automat´ak
´ P´elda. Eszrevessz¨ uk, hogy a 3 v´eg´ allapot ¨osszevonhat´o egyetlen p v´eg´ allapott´ a: b
62/141
A nemdeterminisztkius automata ´ altal´ anos´ıt´ asa: nemdeterminisztikus automata λ-´ atmenettel, r¨ oviden nemdeterminisztikus λ-automata.
a Az M = (Q, Σ, δ, q0 , F ) rendszert nemdeterminisztikus λ-automat´ anak nevezz¨ uk, ahol:
q0
a
b
1. 2. 3. 4. 5.
q0 q1 b q0 q2
a
p
a, b
Q egy nem u ¨res, v´eges halmaz, az ´ allapotok halmaza, Σ egy ´ ab´ec´e, az input ´ ab´ec´e, q0 ∈ Q a kezd˝ o´ allapot, F ⊆ Q a v´eg´ allapotok halmaza, δ : Q × (Σ ∪ {λ}) → P(Q) egy lek´epez´es, az atmenetf¨ ´ uggv´eny.
Olyan ´ atmenet is lehets´eges, amelyik ”nem fogyasztja az inputot”. El˝ onye, hogy n´eha k´enyelmes alkalmazni. Ugyanakkor, a nemdeterminizmushoz hasonl´ oan, nem n¨ oveli meg a felismer˝ o kapacit´ ast.
Az ´ıgy kapott automat´ anak m´ ar csak 4 ´ allapota van. 63/141
64/141
V´eges automat´ak
V´eges automat´ak Egy p´elda:
A λ-´ atmenet λ λ q
p
1 A
´ Atmeneti rel´ aci´ o: (q, w ), (q ′ , w ′ )
(q ′ , w ′ )
∈ C eset´en (q, w ) ⊢M valamely a ∈ (Σ ∪ {λ})-ra ´es q ′ ∈ δ(q, a).
ha w =
1
λ
C
D
0 λ
0
aw ′ ,
B
E
λ 0
λ F
δ
0
1
→A
E
B
B
Felismert nyelv: {1, 11, 0, 01, 00}{0}∗
A felismert nyelv defin´ıci´oja ugyanaz, mint a nemdeterminisztikus esetben: az M automata a w sz´ ot felismeri, ha q0 -b´ ol a w hat´ as´ ara el´erhet˝ o valamely q ∈ F v´eg´ allapot (esetleg a λ-´ atmenetek ”seg´ıts´eg´evel”).
C
D D
⋆D
F
E
F
F
65/141
V´eges automat´ak
C
λ
B, C D
66/141
V´eges automat´ak
T´ etel. Egy nyelv akkor ´es csak akkor ismerhet˝ o fel nemdeterminisztikus λ-automat´ aval, ha felismerhet˝ o nemdeterminisztikus automat´ aval.
Az M = (Q, Σ, δ, q0 , F ) nemdeterminisztikus λ-automat´ ahoz megadunk egy M ′ = (Q, Σ, δ′ , q0 , F ′ ) nemdeterminisztikus automat´at, amelyre L(M ′ ) = L(M).
Bizony´ıt´ as. a) Ha egy nyelv felismerhet˝ o nemdeterminisztikus automat´ aval akkor felismerhet˝ o nemdeterminisztikus λ-automat´ aval is.
M ′ megad´ as´ ahoz, ki kell sz´ amolni az ´ allapotok λ-lez´ ar´ as´ at M-ben. Egy q ∈ Q ´ allapot λ-lez´ ar´ asa azon ´ allapotokb´ol ´ all, amelyek el´erhet˝ ok q-b´ ol λ-´ atmenetekkel: Cl (q) = {p ∈ Q | (q, λ) ⊢∗M (p, λ)}.
b) Ford´ıtva: legyen M = (Q, Σ, δ, q0 , F ) egy nemdeterminisztikus λ-automata. Megadunk egy M ′ = (Q, Σ, δ′ , q0 , F ′ ) nemdeterminisztikus automat´ at, amelyre L(M ′ ) = L(M).
A {q} halmazb´ ol kiindulva, hozz´ avessz¨ uk a q-b´ ol egy λ-´ atmenettel el´erhet˝ o´ allaptokat, ´es ezt az elj´ ar´ ast addig folytatjuk, am´ıg a halmaz b˝ ov´ıthet˝ o. Teh´ at q ∈ Cl (q).
67/141
68/141
V´eges automat´ak
V´eges automat´ak Egy p´elda:
Az M = (Q, Σ, δ, q0 , F ) nemdeterminisztikus λ-automat´ ahoz ′ ′ ′ megadunk egy M = (Q, Σ, δ , q0 , F ) nemdeterminisztikus automat´ at, amelyre L(M ′ ) = L(M).
λ 1
A Cl (q) lez´ ar´ asok ismeret´eben, legyen: S ′ ◮ δ (q, a) = es p∈Cl(q) δ(p, a) ´ ◮
F′
A
= {q ∈ Q | Cl (q) ∩ F 6= ∅}.
◮ ◮ ◮
Ez´ert
L(M ′ )
= L(M).
1
λ
C
D
0 λ
0
Teh´ at M ′ a q ´ allapotb´ ol az a hat´ as´ ara azon ´ allapotokba megy ´ at, amelyekbe M ′ valamennyi λ-´ atmenettel, majd egy a-´ atmenettel jut el. Tov´ abb´ a M ′ v´eg´ allapotai azon ´ allapotok, amelyekb˝ ol M valamennyi λ-´ atmenettel egy F -beli ´ allapotba jut, vagyis felismer. (A ”valamennyi” mindk´et esetben lehet nulla is.)
B
E
λ 0
λ F
Cl (A) = {A}, Cl (B) = {B, D}, Cl (C ) = {C , D},
Cl (D) = {D}, Cl (E ) = {E , B, C , D}, Cl (F ) = {F , D} F ′ = {E , B, C , F , D}
70/141
69/141
V´eges automat´ak
V´eges automat´ak ¨ Osszefoglal´ as:
Egy p´elda:
1
1
B
C
0 0
A
V´eges automat´ akkal nyelveket lehet defini´ alni, oly m´ odon, hogy o minden M automata felismer egy L(M) nyelvet. A k¨ovetkez˝ h´ arom fajta automat´ at ismert¨ uk meg:
D 0
◮
1 0
E
0
determinisztikus automata, nemdeterminisztikus automata, nemdeterminisztikus λ-automata.
A felismer˝ o kapacit´ asa mindh´ arom fajta automat´ anak ugyanaz. Ugyanakkor, a nemdeterminisztikus automat´ akkal ”k¨onnyebb b´ anni”, p´eld´ aul egy adott nyelvhez ´ altal´ aban k¨onnyebb megadni az ot felismer˝ ˝ o nemdeterminisztikus automat´ at, mint a determinisztikusat. Ez m´eg ink´ abb igaz a nemdeterminisztikus λ-automat´ akra. P´eld´ aul k´et atomat´ ahoz nagyon k¨onny˝ u megadni egy olyan nemdeterminisztikus λ-automat´ at, amely az eredeti automat´ak ´ altal felismert nyelvek egyes´ıt´es´et vagy konkaten´ aci´ oj´ at ismeri fel.
F 0
Az ekvivalens nemdeterminisztikus automata. Felismert nyelv: {1, 11, 0, 01, 00}{0}∗ . 71/141
72/141
Regul´aris kifejez´esek
Regul´aris kifejez´esek
Program:
Egy Σ ´ ab´ec´e feletti regul´ aris kifejez´esek halmaza a (Σ ∪ {∅, λ, (, ), +, ∗})∗ halmaz legsz˝ ukebb olyan U r´eszhalmaza, amelyre az al´ abbi felt´etelek teljes¨ ulnek:
Nyelvek megad´ as´ anak egy u ´jabb form´ aj´ aval ismerked¨ unk meg. Vesz¨ unk egy ´ab´ec´et ´es hozz´ avesz¨ unk n´eh´ any seg´edszimb´olumot. Ezekb˝ ol u ´n. regul´ aris kifejez´eseket ´ep´ıt¨ unk fel bizonyos szab´ alyok szerint. Minden regul´ aris kifejez´es meghat´ aroz (vagy: reprezent´ al) egy nyelvet. Az ¨ osszes ilyen nyelvet vizsg´aljuk.
(i) az ∅ (´ ath´ uzott nulla) szimb´ olum eleme U-nak;
(ii) a λ szimb´ olum eleme U-nak;
(iii) Minden a ∈ Σ-ra az a szimb´ olum eleme U-nak;
(iv) Ha R1 , R2 ∈ U, akkor (R1 ) + (R2 ), (R1 )(R2 ), ´es (R1 )∗ is elemei U-nak.
Ki fog der¨ ulni, hogy a regul´ aris kifejez´esekkel reprezent´ alhat´ o nyelvek nem m´ asok, mint a regul´ aris nyelvek.
P´elda: Legyen Σ = {a, b}. Akkor p´eld´ aul a (∅)∗ , ((a) + (b))∗ ´es ((a)(b))((a)∗ ), Σ feletti regul´ aris kifejez´esek.
73/141
Regul´aris kifejez´esek
74/141
Regul´aris kifejez´esek
Az R regul´ aris kifejez´es ´ altal meghat´ arozott (reprezent´ alt ) |R| nyelvet a k¨ovetkez˝ ok´eppen defini´ aljuk:
A (gyakran zavar´ o) z´ ar´ ojelez´es az egy´ertelm˝ u kiolvashat´os´ ag miatt sz¨ uks´eges. A z´ar´ ojelek sz´ ama cs¨ okkenthet˝ o, ha meg´ allapodunk abban, hogy a ∗ priorit´ asi sorrend legyen , konkaten´ aci´ o, +. Tov´ abb´ a, az ∪ ´es konkaten´ aci´ o m˝ uvelet asszociat´ıv, az´ert a + ´es az egym´ as ut´ an ´ır´ as z´ ar´ojelez´ese elhagyhat´o. V´eg¨ ul (a) helyett a-t, (∅) helyett ∅-et ´ırunk.
(i) Ha R = ∅ (´ ath´ uzott nulla), akkor |R| = ∅ (¨ ures nyelv);
(ii) Ha R = λ (mint szimb´ olum), akkor |R| = {λ} (mint nyelv);
(iii) Ha R = a (mint szimb´ olum), akkor |R| = {a} (mint nyelv); (iv) a) Ha R = (R1 ) + (R2 ), akkor |R| = |R1 | ∪ |R2 |; (iv) b) Ha R = (R1 )(R2 ), akkor |R| = |R1 ||R2 |;
´Igy a regul´ aris kifejez´esek z´ ar´ ojelez´ese az al´ abbi m´ odon egyszer˝ us¨ odik:
(iv) c) Ha R = (R1 )∗ , akkor |R| = |R1 |∗ .
Egy L ⊆ Σ∗ nyelv reperzent´ alhat´ o regul´ aris kifejez´essel, ha van olyan Σ feletti R regul´ aris kifejez´es, melyre |R| = L.
(∅)∗ helyett ∅∗ ((a) + (b))∗ helyett (a + b)∗ ((a)(b))((a)∗ ) helyett aba∗ ´ırhatunk (a + b)∗ aba(a + b)∗ -t, a(a + b)∗ b(a + b)∗ a-t, stb. 75/141
76/141
Regul´aris kifejez´esek
Regul´aris kifejez´esek Tov´abbi p´eld´ ak: Σ = {a, b}
P´eld´ ak ◮ ◮ ◮
a) L = {uabav | u, v ∈ Σ∗ } (w ∈ L ⇐⇒ w -ben el˝ ofordul az aba r´esz-sz´ o) reprezent´ alhat´ o, mert
|∅∗ | = |∅|∗ = ∅∗ = {λ};
|(a + b)∗ | = |a + b|∗ = (|a| ∪ |b|)∗ = ({a} ∪ {b})∗ = {a, b}∗ ;
L = |(a + b)∗ aba(a + b)∗ |.
|aba∗ | = |ab||a∗ | = |a||b||a∗ | = |a||b||a|∗ = {a}{b}{a}∗ = {ab}{λ, a, aa, . . .} = {ab, aba, abaa, . . .}.
Gondoljunk az ugyanezen nyelvet felismer˝ o determinisztikus automat´ara. Melyiket k¨onnyebb megadni?
Teh´ at a {λ}, {a, b}∗ ´es {ab, aba, abaa, . . .} nyelvek reprezent´ alhat´ ok regul´ aris kifejez´essel.
odik ´es b) L = {aubva | u, v ∈ Σ∗ } (w ∈ L ⇐⇒ w a-val kezd˝ v´egz˝ odik ´es van benne legal´ abb egy b) reprezent´ alhat´ o, mert
Minden Σ = {a1 , . . . , an } ´ ab´ec´e eset´en a Σ∗ nyelv reprezent´ alhat´ o regul´ aris kifejez´essel, mert Σ∗ = |(a1 + . . . + an )∗ |.
L = |a(a + b)∗ b(a + b)∗ a|.
78/141
77/141
Regul´aris kifejez´esek
Regul´aris kifejez´esek Tov´abbi p´eld´ ak reprezent´ alhat´ o nyelvekre:
Tov´ abbi p´eld´ ak: Σ = {a, b}
d) Minden v´eges nyelv reprezent´ alhat´ o regul´ aris kifejez´essel. Val´ oban, legyen L = {x1 , . . . , xn }, n ≥ 1. Akkor
c) Az (a + ba)∗ (λ + b) regul´ aris kifejez´ere |(a + ba)∗ (λ + b)| =
L = |R1 + . . . + Rn |,
∗
{w ∈ {a, b} | w -ben nem fordul el˝ o a bb r´esz-sz´ o}
ahol
Adjunk meg ehhez a nyelvhez egy determinisztikus automat´ at! Melyik az egyszer˝ ubb?
Ri =
ai1 . . . aini λ
ha xi = ai1 . . . aini ha xi = λ.
P´eld´ aul |λ + a + abaa + abba| = {λ, a, abaa, abba}. Adjunk meg ehhez a nyelvhez is egy determinisztikus automat´ at!
79/141
80/141
Regul´aris kifejez´esek
Regul´aris kifejez´esek
e) Regul´ aris kifejez´esek a UNIX-ban: az ´ ab´ec´e az ASCII ´es k¨ ul¨onb¨oz˝ o r¨ ovid´ıt´eseket enged meg.
e) Regul´aris kifejez´esek a UNIX-ban: az ´ ab´ec´e az ASCII ´es k¨ ul¨onb¨oz˝ o r¨ ovid´ıt´eseket ´es kiterjeszt´eseket enged meg.
R¨ovid´ıt´esek karakter halmazokra:
R¨ovid´ıt´esek m˝ uveletekre:
• A . (pont) a ”tetsz˝ oleges karakter” r¨ ovid´ıt´ese. • Elhagyja a + jeleket: az a1 + . . . + an regul´ aris kifejez´est [a1 . . . an ] form´ aban r¨ ovid´ıti. P´eld´ aul a < + > + = helyett [<>=]-t ´ır. • Kihaszn´ alva, hogy az ASCII rendezett, halmazokat r¨ ovid´ıtve defini´ al. P´eld´aul [0-9] jelenti a 0 + . . . + 9 regul´ aris kifejez´est. Tov´ abbi p´eld´ ak: [A-Z ] ´es [A-Za-z0-9]. • ”Makr´okat” haszn´ al. P´eld´ aul [:digit:] a [0-9] helyett ´es [:alnum:] a [A-Za-z0-9] helyett.
• A + helyett | jelet ´ır. • A ? azt jelenti, hogy legfeljebb egy. Teh´ at az R? UNIX kifejez´es a λ + R r¨ ovid´ıt´ese. • A + viszont azt jelenti, hogy legal´ abb egy. Teh´ at az R+ UNIX ∗ kifejez´es az RR r¨ ovid´ıt´ese. • Az {n} r¨ ovid´ıt´es azt jelenti, hogy n p´eld´ any. Teh´ at az R{5} UNIX kifejez´es az RRRRR r¨ ovid´ıt´ese. P´eld´ ak: .?, [:digit:]+|[:alnum:]{3}, stb.
81/141
Az ekvivalencia t´etel
A regul´aris nyelvek 3-t´ıpus´uak
T´ etel. Tetsz˝oleges L ⊆ Σ∗ nyelv eset´en a k¨ovetkez˝ o h´ arom ´ all´ıt´ as ekvivalens:
1. Lemma. (3) =⇒ (1): Ha L ⊆ Σ∗ nyelv reprezent´ alhat´ o regul´ aris kifejez´essel, akkor gener´ alhat´ o 3-t´ıpus´ u nyelvtannal. Bizony´ıt´ as. Az L-et reprezent´ al´ o R regul´ aris kifejez´es strukt´ ur´ aja szerinti indukci´ oval.
(1) L regul´ aris (gener´ alhat´ o 3-t´ıpus´ u nyelvtannal). (2) L felismerhet˝ o automat´ aval. (3) L reprezent´ alhat´ o regul´ aris kifejez´essel.
Az indukci´ o alapja.
Bizony´ıt´ as. Megmutatjuk, hogy 1. Lemma: (3) 2. Lemma: (1)
=⇒ =⇒
(1) (2)
3. Lemma: (2)
=⇒
(3)
Akkor (1) ⇐⇒ (2) ⇐⇒ (3).
82/141
(i) R = ∅ Ekkor L = |R| = ∅, mely gener´ alhat´ oa G = ({S}, Σ, ∅, S), 3-t´ıpus´ u nyelvtannal. (ii) ´es (iii) R = a, ahol a ∈ Σ vagy a = λ Ekkor L = |R| = {a}, mely gener´ alhat´ o a G = ({S}, Σ, {S → a}, S), 3-t´ıpus´ u nyelvtannal.
⋄
83/141
84/141
A regul´aris nyelvek 3-t´ıpus´uak
A regul´aris nyelvek 3-t´ıpus´uak Akkor L gener´ alhat´ oa
Indukci´ os l´ep´es.
G = (N1 ∪ N2 ∪ {S}, Σ, P1 ∪ P2 ∪ {S → S1 , S → S2 }, S),
(iv) a) R = (R1 ) + (R2 )
3-t´ıpus´ u nyelvtannal, ahol S egy u ´j szimb´ olum.
Ekkor L = |R| = L1 ∪ L2 , ahol L1 = |R1 | ´es L2 = |R2 |. Indukci´ os feltev´es: Li gener´ alhat´ o a Gi = (Ni , Σ, Pi , Si ), 3-t´ıpus´ u nyelvtannal, i = 1, 2. (N1 ∩ N2 = ∅.)
S ⇒∗G w akkor ´es csak akkor, ha S1 ⇒∗G1 w vagy S2 ⇒∗G2 w .
86/141
85/141
A regul´aris nyelvek 3-t´ıpus´uak
A regul´aris nyelvek 3-t´ıpus´uak
Indukci´ os l´ep´es.
◮ ◮
(iv) b) R = (R1 )(R2 )
◮
Ha A → xB ∈ P1 , akkor A → xB ∈ P, Ha A → x ∈ P1 , akkor A → xS2 ∈ P, P2 minden eleme P-nek is eleme.
Ekkor L = |R| = L1 L2 , ahol L1 = |R1 | ´es L2 = |R2 |. S1 ⇒∗G1 w1 ´es S2 ⇒∗G2 w2
alhat´ o a Gi = (Ni , Σ, Pi , Si ), 3-t´ıpus´ u Indukci´ os feltev´es: Li gener´ nyelvtannal, i = 1, 2. (N1 ∩ N2 = ∅.)
akkor ´es csak akkor, ha
Akkor L gener´ alhat´ o a G = (N1 ∪ N2 , Σ, P, S1 ), 3-t´ıpus´ u ukebb olyan szab´ alyhalmaz amire nyelvtannal, ahol P a legsz˝ teljes¨ ulnek a k¨ovetkez˝ o felt´etelek:
S1 ⇒∗G w1 S2 ⇒∗G w1 w2 .
87/141
88/141
A regul´aris nyelvek 3-t´ıpus´uak
A regul´aris nyelvek 3-t´ıpus´uak
Indukci´ os l´ep´es.
◮ ◮
(iv) c) R = (R1 )∗ Ekkor L = |R| =
◮
L∗1 ,
ahol L1 = |R1 |.
S → S1 , S → λ ∈ P,
Ha A → xB ∈ P1 , akkor A → xB ∈ P, Ha A → x ∈ P1 , akkor A → xS ∈ P.
S ⇒G λ
Indukci´ os feltev´es: L1 gener´ alhat´ o a G1 = (N1 , Σ, P1 , S1 ), 3-t´ıpus´ u nyelvtannal.
S ⇒G S1 ⇒∗G w1 S ⇒G w1
Akkor L gener´ alhat´ o a G = (N1 ∪ {S}, Σ, P, S), 3-t´ıpus´ u nyelvtannal, ahol S egy u ´j szimb´ olum, P pedig a legsz˝ ukebb olyan szab´ alyhalmaz amire teljes¨ ulnek a k¨ovetkez˝ o felt´etelek:
(∈ L1 )
w1 S ⇒G w1 S1 ⇒∗G w1 w2 S ⇒G w1 w2 (∈ L1 L1 ) w1 w2 S ⇒G w1 w2 S1 ...
89/141
Az ekvivalencia t´etel
90/141
A 3-t´ıpus´u nyelvek felismerhet˝ok automat´aval
T´ etel. Tetsz˝oleges L ⊆ Σ∗ nyelv eset´en a k¨ovetkez˝ o h´ arom ´ all´ıt´ as ekvivalens:
2. Lemma. (1) =⇒ (2): Ha L ⊆ Σ∗ nyelv regul´ aris, akkor felismerhet˝ o automat´ aval. Bizony´ıt´ as. Legyen L egy regul´ aris nyelv ´es tegy¨ uk fel, hogy L = L(G ), ahol G egy 3-t´ıpus´ u nyelvtan.
(1) L regul´ aris (gener´ alhat´ o 3-t´ıpus´ u nyelvtannal). (2) L felismerhet˝ o automat´ aval. (3) L reprezent´ alhat´ o regul´ aris kifejez´essel.
2.1. Lemma. Minden G = (N, Σ, P, S), 3-t´ıpus´ u nyelvtanhoz megadhat´ o vele ekvivalens G ′ = (N ′ , Σ, P ′ , S), 3-t´ıpus´ u nyelvtan, ′ u ´gy hogy P -ben minden szab´ aly A → B, A → aB vagy A → λ alak´ u, ahol A, B ∈ N ´es a ∈ Σ.
Bizony´ıt´ as. 1. Lemma: (3) 2. Lemma: (1)
=⇒ =⇒
(1) (2)
3. Lemma: (2)
=⇒
(3)
√
2.2. Lemma. Minden olyan G = (N, Σ, P, S), 3-t´ıpus´ u nyelvtanhoz melynek csak A → B, A → aB vagy A → λ alak´ u szab´ alyai vannak megadhat´ o olyan M = (Q, Σ, δ, q0 , F ) nemdeterminisztkius λ-automata, amelyre L(M) = L(G ).
91/141
92/141
A 3-t´ıpus´u nyelvek felismerhet˝ok automat´aval
A 3-t´ıpus´u nyelvek felismerhet˝ok automat´aval (ii) Minden A → a1 . . . an B, P-beli szab´ aly eset´en (ahol n > 1, uk fel P ′ -be az a1 , . . . , an ∈ Σ) vegy¨
2.1. Lemma. Minden G = (N, Σ, P, S), 3-t´ıpus´ u nyelvtanhoz u nyelvtan, megadhat´ o vele ekvivalens G ′ = (N ′ , Σ, P ′ , S), 3-t´ıpus´ ′ u ´gy hogy P -ben minden szab´ aly A → B, A → aB vagy A → λ alak´ u, ahol A, B ∈ N ´es a ∈ Σ.
A → a1 A1 , A1 → a2 A2 , . . . , An−1 → an B szab´ alyokat, ahol A1 , . . . , An−1 u ´j nemtermin´ alis szimb´ olumok.
Bizony´ıt´ as. Konstru´ aljuk meg P ′ -t a k¨ovetkez˝ ok´eppen:
(iii) Minden A → a1 . . . an , P-beli szab´ aly eset´en (ahol n ≥ 1, a1 , . . . , an ∈ Σ) vegy¨ uk fel P ′ -be az
(i) Minden A → B, A → aB ´es A → λ alak´ u P-beli szab´ alyt vegy¨ unk fel P ′ -be.
A → a1 A1 , A1 → a2 A2 , . . . , An−1 → an An , An → λ szab´ alyokat, ahol A1 , . . . , An u ´j nemtermin´ alisok. ′ Legyen N = N ∪ { u ´j nemtermin´ alisok }.
94/141
93/141
A 3-t´ıpus´u nyelvek felismerhet˝ok automat´aval
A 3-t´ıpus´u nyelvek felismerhet˝ok automat´aval
Minden A ∈ N-re ´es w ∈ Σ∗ -ra
P´elda a szab´ alyok sz´etdarabol´ as´ ara
A ⇒∗G w akkor ´es csak akkor, ha A ⇒∗G ′ w .
S → abA | bB A → bbB | λ B → ab | bA ′ G : S → aA1 , A1 → A → bA2 , A2 → B → aA3 , A3 → B → bA G:
Ugyanis A → a1 . . . an B ∈ P akkor ´es csak akkor, ha A ⇒G ′ a1 A1 ⇒G ′ . . . ⇒G ′ a1 . . . an−1 An−1 ⇒G ′ a1 . . . an B ´es
bA, bB, bA4 ,
S A A4
→ → →
bB λ λ
A → a1 . . . an ∈ P akkor ´es csak akkor, ha A ⇒G ′ a 1 A 1 ⇒G ′ . . . ⇒G ′ a 1 . . . a n A n ⇒G ′ a 1 . . . a n . Az A = S v´ alaszt´ assal kapjuk, hogy L(G ) = L(G ′ ).
95/141
96/141
A 3-t´ıpus´u nyelvek felismerhet˝ok automat´aval
A 3-t´ıpus´u nyelvek felismerhet˝ok automat´aval
2.2. Lemma. Minden olyan G = (N, Σ, P, S), 3-t´ıpus´ u u nyelvtanhoz melynek csak A → B, A → aB vagy A → λ alak´ szab´ alyai vannak megadhat´ o olyan M = (Q, Σ, δ, q0 , F ) nemdeterminisztkius λ-automata, amelyre L(M) = L(G ).
M-ben:
G -ben:
Bizony´ıt´ as. Konstru´ aljuk meg M-et a k¨ovetkez˝ ok´eppen: Q = N,
◮
q0 = S,
◮
F = {B ∈ N | B → λ ∈ P},
◮
a
1 0 0 1 11111111 00000000 0 1 0 1
A → aB ∈ P
◮
A
B
⇔ B →λ∈P
minden A ∈ N ´es a ∈ (Σ ∪ {λ}) eset´en legyen δ(A, a) = {B ∈ N | A → aB ∈ P}.
B∈F Az ´ abr´ an a ∈ Σ vagy a = λ.
97/141
A 3-t´ıpus´u nyelvek felismerhet˝ok automat´aval
98/141
A 3-t´ıpus´u nyelvek felismerhet˝ok automat´aval
Ekkor minden n ≥ 1, A, B ∈ N ´es w ∈ Σ∗ eset´en
P´eld´ aul, vegy¨ uk az el˝ obbi G ′ nyelvtant:
A ⇒nG wB akkor ´es csak akkor ha (A, w ) ⊢nM (B, λ). R´eszletesebben:
G′ :
A ⇒G a1 A1 ⇒G . . . ⇒G a1 . . . an−1 An−1 ⇒G a1 . . . an B akkor ´es csak akkor, ha
S A B B
→ → → →
aA1 , bA2 , aA3 , bA
A1 A2 A3
→ → →
bA, bB, bA4 ,
S A A4
→ → →
bB λ λ
(A, a1 . . . an ) ⊢M (A1 , a2 . . . an ) ⊢M . . . ⊢M (B, λ). alaszt´ assal ad´ odik, hogy L(M) = L(G ). Az A = S, B ∈ F v´
99/141
100/141
A 3-t´ıpus´u nyelvek felismerhet˝ok automat´aval
A 3-t´ıpus´u nyelvek felismerhet˝ok automat´aval Egy megjegyz´es a 2.2 Lemm´ ahoz:
A G ′ -h¨oz tartoz´o automata
A1 a
A lemma bizony´ıt´ as´ aban alkalmazott konstrukci´ o k¨onnyen ”megford´ıthat´o”, vagyis tetsz˝ oleges M nemdeterminisztikus λ-automat´ ahoz meg tudunk adni egy olyan G regul´ aris nyelvtant, amelyre L(G ) = L(M). Val´ oban, a nyelvtan nemtermin´ alisai az automata ´ allapotai lesznek. Tov´ abb´ a, ha az automat´ aban valamely q ´ allapotb´ ol egy a ∈ (Σ ∪ {λ}) szimb´ olum hat´ as´ ara egy p ´ allapotba jutunk (azaz p ∈ δ(q, a)), akkor a nyelvtanba felvessz¨ uk a q → ap szab´ alyt. V´eg¨ ul minden q v´eg´ allapot eset´en a nyelvtanba felvessz¨ uk a q → λ szab´ alyt.
b
b S
A2
A
b b
b a
b
B
A3
A4
Ezzel a bizony´ıtottuk, hogy (2) =⇒ (1). A t´etel bizony´ıt´ as´ ahoz viszont m´eg a (2) =⇒ (3) l´ep´es hi´ anyzik.
102/141
101/141
Az ekvivalencia t´etel
Az automat´aval felismerhet˝o nyelvek regul´arisak
T´ etel. Tetsz˝oleges L ⊆ Σ∗ nyelv eset´en a k¨ovetkez˝ o h´ arom ´ all´ıt´ as ekvivalens:
Lemma 3. (2) =⇒ (3): Minden, automat´ aval felismerhet˝ o nyelv reprezent´ alhat´ o regul´ aris kifejez´essel. (S. C. Kleene t´etele, 1956.)
(1) L regul´ aris (gener´ alhat´ o 3-t´ıpus´ u nyelvtannal),
Bizony´ıt´ as. Legyen L = L(M), ahol M = (Q, Σ, δ, q0 , F ) determinisztikus automata. Megadunk egy olyan regul´ aris kifejez´est, amely L-et reprezent´ alja. T´etelezz¨ uk fel, hogy Q = {1, . . . , n} ´es q0 = 1. (k) Minden 0 ≤ k ≤ n ´es 1 ≤ i , j ≤ n eset´en defini´ aljuk a Li ,j ⊆ Σ∗ nyelvet a k¨ovetkez˝ ok´eppen: (k) x ∈ Li ,j ⇐⇒ (i , x) ⊢∗M (j, λ) ´es
(2) L felismerhet˝ o automat´ aval. (3) L reprezent´ alhat´ o regul´ aris kifejez´essel. Bizony´ıt´ as. 1. Lemma: (3) 2. Lemma: (1)
=⇒ =⇒
√ (1) √ (2)
3. Lemma: (2)
=⇒
(3)
+ ′ ′ minden (i , x) ⊢+ en M (i , x ) ⊢M (j, λ) eset´
i ′ ∈ {1, . . . , k}.
103/141
104/141
Az automat´aval felismerhet˝o nyelvek regul´arisak
Az automat´aval felismerhet˝o nyelvek regul´arisak Mivel
(k)
Az Li ,j nyelvet alkot´o x szavak:
L(M) =
[
(n)
L1,j ,
j∈F (n)
elegend˝ o megadni minden j ∈ F -re egy L1,j -t reprezent´ al´ o regul´ aris kifejez´est. (n) (n) Ha ugyanis L1,j = |R1,j |, akkor
x 0 0 0 0 0 0 1 1 1 1 1 1 1111111111111111111 0000000000000000000 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1
i
⊆ {1, . . . , k}
L(M) = |R1,j1 + . . . + R1,jl |,
j
ahol F = {j1 , . . . , jl }. T¨ obbet bizony´ıtunk: minden 0 ≤ k ≤ n-ra ´es 1 ≤ i , j ≤ n-re (k) megadunk egy Ri ,j regul´ aris kifejez´est, melyre (k)
(k)
|Ri ,j | = Li ,j . 105/141
Az automat´aval felismerhet˝o nyelvek regul´arisak
106/141
Az automat´aval felismerhet˝o nyelvek regul´arisak
(k)
Ri ,j megad´ asa k szerinti indukci´ oval. k = 0: {a ∈ Σ | δ(i , a) = j}, ha i = 6 j (0) Li ,j = {a ∈ Σ | δ(i , a) = j} ∪ {λ}, ha i = j.
k ⇒ k + 1: (k)
(k)
(k+1)
=⇒ megadjuk minden i , j-re Ri ,j
a1 i
a1 , . . . , at
..
1 0 0 1
1 0 0 1
j
-t
El˝ osz¨ or is ´eszrevessz¨ uk (!), hogy 1 0 0i 1
=j
(k+1)
Li ,j
at
(0)
(k)
tfh minden i , j-re megadtuk Ri ,j -t, melyre |Ri ,j | = Li ,j
(k)
(k)
(k)
(k)
= Li ,j ∪ Li ,k+1 (Lk+1,k+1 )∗ Lk+1,j .
(0)
Ri ,j = a1 + . . . + at vagy Ri ,j = a1 + . . . + at + λ (0)
(0)
Mindk´et esetben |Ri ,j | = Li ,j . 107/141
108/141
Az automat´aval felismerhet˝o nyelvek regul´arisak (k+1)
Li ,j
(k)
(k)
(k)
Az automat´aval felismerhet˝o nyelvek regul´arisak
(k)
= Li ,j ∪ Li ,k+1 (Lk+1,k+1 )∗ Lk+1,j
Legyen (k+1)
Ri ,j
(k)
(k)
(k)
(k)
(k)
= Ri ,j + Ri ,k+1 (Rk+1,k+1 )∗ Rk+1,j .
Lk+1,k+1 Ekkor (k+1)
|Ri ,j
0 0 0 1 1 1 1111111111111 0000000000000 1111111111111 0000000000000 0 0 0 1 1 1 0 0 0 1 1 1 i k + 1 j (k) (k) Lk+1,j Li ,k+1
(k)
(k)
(k)
(k)
| = |Ri ,j | ∪ |Ri ,k+1 ||Rk+1,k+1 |∗ |Rk+1,j | (k)
(k)
(k)
(k)
(k+1)
= Li ,j ∪ Li ,k+1 (Lk+1,k+1 )∗ Lk+1,j = Li ,j Mint l´ attuk, L(M) = |R1,j1 + . . . + R1,jl |.
109/141
Az ekvivalencia t´etel
110/141
Az ekvivalencia t´etel ¨ Osszefoglal´ as:
T´ etel. Tetsz˝oleges L ⊆ Σ∗ nyelv eset´en a k¨ovetkez˝ o h´ arom ´ all´ıt´ as ekvivalens:
A k¨ovetkez˝ o eszk¨oz¨ ok mindegyik´evel a regul´ aris nyelveket reprezent´ alhatjuk:
(1) L regul´ aris (gener´ alhat´ o 3-t´ıpus´ u nyelvtannal), (2) L felismerhet˝ o automat´ aval. (3) L reprezent´ alhat´ o regul´ aris kifejez´essel.
◮
regul´ aris (3-t´ıpus´ u) nyelvtanok,
◮
regul´ aris nyelvtanok, amelyek minden szab´ alya A → B, A → aB vagy A → λ alak´ u,
Bizony´ıt´ as. 1. Lemma: (3) 2. Lemma: (1)
=⇒ =⇒
3. Lemma: (2)
=⇒
Teh´ at (1) ⇐⇒ (2) ⇐⇒ (3).
√ (1) √ (2) √ (3) ⋄
◮
determinisztikus automat´ ak,
◮
nemdeterminisztikus automat´ ak,
◮
nemdeterminisztikus λ-automat´ ak,
◮
regul´ aris kifejez´esek.
A tov´ abbiakban, ha vesz¨ unk egy regul´ aris nyelvet valamilyen probl´ema megold´ as´ ara, akkor mindig azt a reprezent´ aci´ ot v´ alasztjuk, ami a legc´elszer˝ ubb az adott probl´ema szempontj´ ab´ ol. 111/141
112/141
A Chomsky nyelvoszt´alyok g´epi reprezent´aci´oi
Pump´al´o lemma regul´aris nyelvekre Lemma. (Pump´ al´ o lemma regul´ aris nyelvekre.) aris nyelv eset´en Minden L ⊆ Σ∗ regul´
G´epi reprezent´ aci´ o:
- megadhat´ o olyan (L-t˝ol f¨ ugg˝ o) k > 0 eg´esz sz´ am, hogy
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 ? ? ?
- minden w ∈ L-re,
Det. vs nemdet. det. = nemdet. ? ? ?
- ha |w | ≥ k, akkor van olyan w = w1 w2 w3 felbont´ as, melyre 1) 0 < |w2 | ´es |w1 w2 | ≤ k,
2) minden n ≥ 0-ra, w1 w2n w3 ∈ L. (Sz¨ uks´eges felt´etele annak, hogy egy nyelv regul´ aris legyen. Ha egy nyelv nem teljes´ıti ezt a felt´etelt, akkor az nem regul´ aris.)
114/141
113/141
Pump´al´o lemma regul´aris nyelvekre
Pump´al´o lemma regul´aris nyelvekre Mivel K ≥ ||Q||, a q0 , q1 , . . . , qK sorozaban legal´ abb egy ´ allapot k´etszer is szerepel (skatulya elv = pigeon hole principle). Legyen qj a legels˝o olyan ´ allapot, amelyik a sorozatban m´ ar kor´ abban is el˝ ofordul: van olyan i < j, hogy qi = qj .
Bizony´ıt´ as. Mivel L regul´ aris, van olyan M = (Q, Σ, δ, q0 , F ) determinisztikus automata, melyre L = L(M). Legyen k = ||Q|| (az ´ allapotok sz´ ama). Ez a k j´o lesz. Vegy¨ unk egy w ∈ L sz´ ot u ´gy, hogy |w | ≥ k. Akkor w = a1 a2 . . . aK , ahol K ≥ k ´es vannak olyan q1 , q2 , . . . , qK ∈ Q allapotok, melyekre ´ (q0 , a1 . . . aK )
tov´ abb´ a qK ∈ F .
⊢ ⊢ ... ⊢ ⊢
Legyenek w1 = a1 . . . ai , w2 = ai +1 . . . aj ´es w3 = aj+1 . . . aK . (Ha i = 0 akkor w1 = λ, ha j = K akkor w3 = λ) Nyilv´ anval´o, hogy w = w1 w2 w3 . Tov´ abb´ a,
(q1 , a2 . . . aK ) (q2 , a3 . . . aK )
1) 0 < |w2 |, mert i < j ´es |w1 w2 | ≤ k, mert qj a legels˝o olyan a´llapot, amelyik a sorozatban m´ ar kor´ abban is el˝ ofordul.
(qK −1 , aK ) (qK , λ),
´es ...
115/141
116/141
Pump´al´o lemma regul´aris nyelvekre
Pump´al´o lemma regul´aris nyelvekre A Pump´ al´ o lemma egy k¨ovetkezm´enye:
2) Minden n ≥ 0-ra w1 w2n w3 ∈ L:
Lemma. Az L = {an b n | n ≥ 0} nyelv nem regul´ aris. Bizony´ıt´ as. Tegy¨ uk fel, hogy igen (indirekt bizony´ıt´ as). Legyen k a pump´ al´ o lemma szerint az L-hez tartoz´o sz´ am, ´es vegy¨ uk az ak b k ∈ L sz´ ot, melynek hossza 2k ≥ k. A pump´al´ o lemma miatt l´etezik ak b k = w1 w2 w3 felbont´ as, melyre n 0 < |w2 |, |w1 w2 | ≤ k ´es minden n ≥ 0-ra w1 w2 w3 ∈ L.
w2
q0
w1
w3
qK
qi = qj
Mivel |w1 w2 | ≤ k, a k¨oz´eps˝ o |w2 | sz´ o csak a bet˝ ukb˝ol ´ all. Tov´ abb´ a a 0 < |w2 | felt´etel miatt a w1 w22 w3 , w1 w23 w3 , stb szavakban az a-k sz´ ama nagyobb mint a b-k sz´ ama, teh´ at ezen szavak egyike sincs L-ben. Ellentmond´ as, teh´ at L nem regul´ aris.
117/141
Pump´al´o lemma regul´aris nyelvekre
118/141
Pump´al´o lemma regul´aris nyelvekre
Intu´ıci´o:
A Pump´ al´ o lemma egy tov´ abbi k¨ovetkezm´enye: van olyan k¨ornyezetf¨ uggetlen nyelv, amelyik nem regul´ aris.
Egy automata nem k´epes sz´ amolni, hogy k´et bet˝ u ugyanannyiszor szerepel-e.
T´ etel. L3 ⊂ L2 . Bizony´ıt´ as.
De kezelj¨ uk ezt ´ ovatosan! Az al´ abbi nyelv regul´ aris: a) L3 ⊆ L2 , mivel minden regul´ aris nyelvtan k¨ornyezetf¨ uggetlen.
{w ∈ {a, b}∗ | w -ben az ab ´es a ba alak´ u r´esz-szavak sz´ ama megegyezik}.
b) Az {an b n | n ≥ 0} nyelv L2 -beli, mivel gener´ alhat´ o az S → aSb | λ
Bizony´ıt´ as HF.
szab´ alyokb´ ol ´ all´o k¨ornyezetf¨ uggetlen nyelvtannal. Ugyanakkor, mint l´ attuk L 6∈ L3 .
119/141
120/141
Regul´aris nyelvek z´arts´agi tulajdons´agai
Regul´aris nyelvek z´arts´agi tulajdons´agai
M˝ uveletekre val´o z´ arts´ ag ´ altal´ aban:
Regul´ aris m˝ uveletek: ∪, konkaten´ aci´ o, ∗ .
Legyen C nyelvek egy oszt´ alya (pl. regul´ aris nyelvek, k¨ornyezef¨ uggetlen nyelvek) ´es
T´ etel. A regul´ aris nyelvek oszt´ alya z´ art a regul´ aris m˝ uveletekre.
• : P(Σ∗ ) × P(Σ∗ ) → P(Σ∗ ),
Bizony´ıt´ as. A regul´ aris nyelveket regul´ aris kifejez´esekkel reprezent´ aljuk. El˝ osz¨ or az ∪-ra val´o z´ arts´ agot bizony´ıtjuk.
(L1 , L2 ) 7→ L1 • L2
egy k´etv´ altoz´os m˝ uvelet nyelvekkel. (P´eld´ aul: egyes´ıt´es, konkaten´ aci´ o, stb.)
Legyenek L1 , L2 regul´ aris nyelvek. Megadunk egy olyan R regul´ aris kifejez´est, melyre |R| = L1 ∪ L2 .
Azt mondjuk, hogy C z´ art a • m˝ uveletre, ha tetsz˝ oleges L1 , L2 ∈ C eset´en, L1 • L2 ∈ C.
Mivel L1 , L2 regul´ aris, vannak olyan R1 , R2 regul´ aris kifejez´esek, melyekre L1 = |R1 | ´es L2 = |R2 |. Legyen R = (R1 ) + (R2 ). Ekkor |R| = |R1 + R2 | = |R1 | ∪ |R2 | = L1 ∪ L2 , teh´ at L1 ∪ L2 is regul´ aris. A konkaten´ aci´ ora ´es a ∗ -ra val´o z´ arts´ ag hasonl´ oan bizony´ıthat´o.
Az egy´ altoz´os m˝ uveletekre (pl. komplementer, iter´ aci´ o) val´o z´ arts´ ag hasonl´ oan defini´ alhat´ o.
121/141
Regul´aris nyelvek z´arts´agi tulajdons´agai
122/141
Regul´aris nyelvek z´arts´agi tulajdons´agai Automat´ ak direkt szorzata:
Boole m˝ uveletek: ∪, ∩, komplementer.
Az M1 = (Q1 , Σ, δ1 , q1 , F1 ) ´es M2 = (Q2 , Σ, δ2 , q2 , F2 ) determinisztikus automat´ ak egy direkt szorzata az M = (Q1 × Q2 , Σ, δ, [q1 , q2 ], F ) automata, ahol minden p1 ∈ Q1 ´es p2 ∈ Q2 ´ allapot ´es a ∈ Σ input szimb´ olum eset´en
T´ etel. A regul´ aris nyelvek oszt´ alya z´ art a Boole m˝ uveletekre. Bizony´ıt´ as. A regul´ aris nyelveket most determinisztikus automat´ akkal reprezent´ aljuk.
δ([p1 , p2 ], a) = [δ1 (p1 , a), δ2 (p2 , a)], A bizony´ıt´ asban az automat´ ak direkt szorzata konstrukci´ ot alkalmazzuk.
tov´abb´ a F ⊆ Q1 × Q2 (k´es˝ obb adjuk meg pontosan). Az M ´ allapotai teh´ at [p1 , p2 ] alak´ u p´ arok. Az M1 ´es M2 automat´akat p´ arhuzamosan m˝ uk¨ odtetj¨ uk: ha M1 p1 -b˝ ol az a hat´ as´ ara r1 -be, M2 p2 -b˝ ol az a hat´ as´ ara r2 -be megy ´ at, akkor M [p1 , p2 ]-b˝ ol az a hat´ as´ ara [r1 , r2 ]-be megy ´ at.
123/141
124/141
Regul´aris nyelvek z´arts´agi tulajdons´agai
Regul´aris nyelvek z´arts´agi tulajdons´agai A Boole m˝ uveletekre val´o z´ arts´ ag bizony´ıt´ asa: legyenek L1 = L(M1 ) ´es L2 = L(M2 ) regul´ aris nyelvek, ahol M1 ´es M2 a fenti determinisztikus automat´ ak. Konstru´ aljuk meg az M direkt szorzat automat´ at.
Ekkor minden p1 , r1 ∈ Q1 , p2 , r2 ∈ Q2 ´es x ∈ Σ∗ eset´eben ([p1 , p2 ], x) ⊢∗M ([r1 , r2 ], λ) m
a) Ha F = F1 × F2 , akkor L(M) = L(M1 ) ∩ L(M2 ). Teh´ at L1 ∩ L2 is regul´ aris.
(p1 , x) ⊢∗M1 (r1 , λ) ´es (p2 , x) ⊢∗M2 (r2 , λ).
b) Ha F = F1 × (Q2 − F2 ), akkor L(M) = L(M1 ) − L(M2 ). Teh´ at L1 − L2 is regul´ aris. K¨ovetkezm´eny: Mivel a Σ∗ nyelv regul´ aris (nyilv´ anval´o), az ∗ L1 = Σ − L1 is regul´ aris.
Vagyis M a szavakon is M1 ´es M2 p´ arhuzamos m˝ uk¨ od´es´et szimul´ alja.
c) Ha F = (F1 × Q2 ) ∪ (Q1 × F2 ), akkor L(M) = L(M1 ) ∪ L(M2 ). ´ Teh´at L1 ∪ L2 regul´ aris. (Ujabb bizony´ıt´ as.) 125/141
Regul´aris nyelvek z´arts´agi tulajdons´agai
126/141
Regul´aris nyelvek z´arts´agi tulajdons´agai
Egy megjegyz´es:
¨ Osszefoglal´ as:
A komplementerre val´o z´ arts´ ag egyszer˝ ubben is bizony´ıthat´o. aris, akkor felismerhet˝ o egy Val´ oban, ha az L nyelv regul´ M = (Q, Σ, δ, q0 , F ) determinisztikus automat´ aval. De akkor az M ′ = (Q, Σ, δ, q0 , Q − F ) automata az L nyelvet ismeri fel, mert pontosan azok a szavak viszik v´eg´ allapotba, amelyek M-et Q − F -be, vagyis nem v´eg´ allapotba viszik. Ez´ert az L nyelv is regul´ aris.
M˝ uvelet ∪ konkaten´ aci´ o ∗
∩ komplementer
127/141
Z´ arts´ ag igen igen igen igen igen
128/141
Eld¨ont´esi k´erd´esek regul´aris nyelvekre
Eld¨ont´esi k´erd´esek regul´aris nyelvekre
Az eld¨ont´esi k´erd´esekr˝ ol ´ altal´ aban. Ebben a r´eszben a regul´ aris nyelvek oszt´ aly´ ara vonatkoz´ o eld¨ont´esi k´erd´esekkel foglalkozunk. A fejezet sor´ an a regul´ aris nyelveket determinisztikus automat´ akkal reprezent´ aljuk.
Egy eld¨ont´esi k´erd´es mindig egy nyelvoszt´ alyra (pl regul´ aris nyelvek, k¨ornyezetf¨ uggetlen nyelvek) ´es egy nyelvekre vonatkoz´ o tulajdons´ agra (pl. u ¨ress´eg, v´egess´eg) ´ertend˝o ´es u ´gy sz´ ol, hogy l´etezik-e olyan algoritmus, amelynek inputja a nyelvoszt´ aly tetsz˝ oleges eleme, outputja pedig ”Igen” ha a nyelv rendelkezik az adott tulandons´ aggal, k¨ ul¨onben pedig ”Nem”.
Teh´at, ha azt mondjuk, hogy adott egy L regul´ aris nyelv, akkor ez alatt azt ´ertj¨ uk, hogy adott egy determinisztikus M automata, amelyre L = L(M).
P´eld´ aul, l´etezik-e olyan algoritmus, amelynek inputja egy tetsz˝ oleges regul´ aris nyelv (vagyis e nyelvet reprezent´ al´ o determinisztikus automata), outputja pedig ”Igen” ha a nyelv v´egtelen, k¨ ul¨onben pedig ”Nem”. Ugyanez k´erdezhet˝o a k¨ornyezetf¨ uggetlen nyelvekre is.
Mint l´ atni fogjuk, a regul´ aris nyelvek valamennyi, ´ altalunk vizsg´ alt tulajdons´ aga eld¨onthet˝ o. Magasabb nyelvoszt´ alyok eset´en pedig egyre t¨obb olyan tulajdons´ ag lesz, ami nem eld¨onthet˝ o.
A k´erd´esnek csak akkor van ´ertelme, ha az input nyelvet valamilyen eszk¨ozzel reprezen´ aljuk. 129/141
Eld¨ont´esi k´erd´esek regul´aris nyelvekre
130/141
Eld¨ont´esi k´erd´esek regul´aris nyelvekre ¨ Uress´ egi probl´ema
Eleme-e probl´ema Probl´ema: Eld¨onthet˝ o-e tetsz˝ oleges w sz´o ´es L regul´ aris nyelv eset´en, hogy teljes¨ ul-e w ∈ L?
Probl´ema: Eld¨onthet˝ o-e tetsz˝ oleges L regul´ aris nyelv eset´en, hogy teljes¨ ul-e L = ∅?
T´ etel. Az eleme-e probl´ema regul´ aris nyelvekre eld¨onthet˝ o.
T´ etel. Az u ¨ress´egi probl´ema regul´ aris nyelvekre eld¨onthet˝ o. o ´es egy M = (Q, Σ, δ, q0 , F ) automat´ aval Input: Egy w sz´ megadott L regul´ aris nyelv (teh´ at L = L(M)). Output: ”Igen” ha w ∈ L, k¨ ul¨onben ”Nem”.
Input: Egy M = (Q, Σ, δ, q0 , F ) automat´ aval megadott L regul´ aris nyelv. Output: ”Igen”, ha L = ∅, k¨ ul¨onben ”Nem”.
Algoritmus: Hat´ arozzuk meg azt a q ´ allpotot, amelybe az automata q0 -b´ ol a w hat´ as´ ara ker¨ ul. Ha q ∈ F , akkor a v´ alasz ”Igen”, k¨ ul¨onben ”Nem”.
131/141
132/141
Eld¨ont´esi k´erd´esek regul´aris nyelvekre
Eld¨ont´esi k´erd´esek regul´aris nyelvekre
¨ Uress´ egi probl´ema
V´egtelen-e probl´ema
Algoritmus:
Lemma. Legyen M = (Q, Σ, δ, q0 , F ) egy automata ´es legyen k = ||Q||. Az L(M) nyelv akkor ´es csak akkor v´egtelen, ha van olyan x ∈ L(M), melyre k ≤ |x| < 2k.
(1) Sz´ amoljuk ki a q0 -b´ ol el´erhet˝ o´ allapotok Q ′ halmaz´ at a Q0 , Q1 , . . . ´ allapothalmaz-sorozat seg´ıts´eg´evel.
Bizony´ıt´ as. ⇐-ir´ any: Tfh ∃x ∈ L(M), melyre |x| ≥ k. Akkor a pump´ al´ o lemma szerint ∃ x = x1 x2 x3 felbont´ as, melyre 0 < |x2 | ≤ k ´es minden n ≥ 0-ra x1 x2n x3 ∈ L(M). K¨ovetkez´esk´eppen L(M) v´egtelen. ⇒-ir´ any: Tfh L(M) v´egtelen. Akkor ∃ x ∈ L(M) melyre |x| ≥ 2k. Mivel |x| ≥ k, a pump´ al´ o lemma miatt ∃ x = x1 x2 x3 felbont´ as, ′ ′ melyre 0 < |x2 | ≤ k ´es x = x1 x3 ∈ L(M). Ha ekkor |x | ≥ 2k, akkor ism´etelj¨ uk az elj´ ar´ ast x ′ -re addig, am´ıg |x ′ | < 2k nem lesz.
(i) Legyen Q0 = {q0 } ´es i = 0.
(ii) Legyen Qi +1 = Qi ∪ {δ(q, a) | q ∈ Qi ´es a ∈ Σ}.
(iii) Ha Qi = Qi +1 , akkor Q ′ = Qi (´es stop), k¨ ul¨onben i = i + 1 ´es goto (ii). (2) Ha Q ′ ∩ F = ∅, akkor a v´ alasz ”Igen”, k¨ ul¨onben ”Nem”.
133/141
Eld¨ont´esi k´erd´esek regul´aris nyelvekre
134/141
Eld¨ont´esi k´erd´esek regul´aris nyelvekre
V´egtelen-e probl´ema
V´egtelen-e probl´ema
Probl´ema: Eld¨onthet˝ o-e tetsz˝ oleges L regul´ aris nyelv eset´en, hogy L v´egtelen-e?
Algoritmus: Legyen k = ||Q||. Sz´ amoljuk ki minden 0 ≤ i < 2k eset´en a q0 -b´ ol az i hossz´ us´ ag´ u szavakkal el´erhet˝ o´ allapotok Qi halmaz´ at:
T´ etel. A v´egtelen-e probl´ema regul´ aris nyelvekre eld¨onthet˝ o. (i) Ha i = 0 akkor Qi = {q0 }, k¨ ul¨onben
Input: Egy M = (Q, Σ, δ, q0 , F ) automat´ aval megadott L regul´ aris nyelv.
(ii) Qi = {δ(q, a) | q ∈ Qi −1 ´es a ∈ Σ}.
Output: ”Igen”, ha L v´egtelen, k¨ ul¨onben ”Nem”.
Ezut´ an minden i -re, melyre k ≤ i < 2k, vizsg´ aljuk meg, hogy Qi ∩ F 6= ∅ teljes¨ ul-e. Ha valamely i -re teljes¨ ul, akkor L(M) v´egtelen, teh´ at a v´ alasz ”Igen”, k¨ ul¨onben a v´ alasz ”Nem”.
135/141
136/141
Eld¨ont´esi k´erd´esek regul´aris nyelvekre
Eld¨ont´esi k´erd´esek regul´aris nyelvekre
Tartalmaz´ asi probl´ema
Tartalmaz´ asi probl´ema
Probl´ema: Eld¨onthet˝ o-e tetsz˝ oleges L1 , L2 regul´ aris nyelvek eset´en, hogy L1 ⊆ L2 teljes¨ ul-e?
Algoritmus: Konstru´ aljuk meg az M = (Q1 × Q2 , Σ, δ, (q1 , q2 ), F ) automat´at, ahol F = F1 × (Q2 − F2 ). (Ismert, hogy ekkor L(M) = L1 − L2 .) D¨ onts¨ uk el, hogy L(M) = ∅ teljes¨ ul-e (a regul´ aris nyelvek u ¨ress´ege eld¨onthet˝ o). Ha teljes¨ ul, akkor a v´ alasz ”Igen”, k¨ ul¨onben a v´ alasz ”Nem”.
T´ etel. A tartalmaz´ asi probl´ema regul´ aris nyelvekre eld¨onthet˝ o. Input: Az M1 = (Q1 , Σ, δ1 , q1 , F1 ) ´es M2 = (Q2 , Σ, δ2 , q2 , F2 ) automat´ akkal adott L1 = L(M1 ) ´es L2 = L(M2 ) regul´ aris nyelvek.
(Az algoritmus azon a t´enyen alapul, hogy L1 ⊆ L2 akkor ´es csak akkor, ha L1 − L2 = ∅.) ⋄
Output: ”Igen”, ha L1 ⊆ L2 , k¨ ul¨onben ”Nem”.
137/141
Eld¨ont´esi k´erd´esek regul´aris nyelvekre
138/141
Eld¨ont´esi k´erd´esek regul´aris nyelvekre
Ekvivalencia probl´ema
Ekvivalencia probl´ema
Probl´ema: Eld¨onthet˝ o-e tetsz˝ oleges L1 , L2 regul´ aris nyelvek eset´en, ul-e? hogy L1 = L2 teljes¨
Algoritmus: Alkalmazzuk k´etszer a tartalmaz´ as eld¨ont´esi algoritmus´ at ´es d¨ onts¨ uk el, hogy az L1 ⊆ L2 ´es az L2 ⊆ L1 tartalmaz´ asok teljes¨ ulnek-e. Ha mindkett˝ o teljes¨ ul, akkor a v´ alasz ”Igen”, k¨ ul¨onben a v´ alasz ”Nem”.
T´ etel. Az ekvivalencia probl´ema regul´ aris nyelvekre eld¨onthet˝ o. Input: Az M1 = (Q1 , Σ, δ1 , q1 , F1 ) ´es M2 = (Q2 , Σ, δ2 , q2 , F2 ) automat´ akkal adott L1 = L(M1 ) ´es L2 = L(M2 ) regul´ aris nyelvek.
(Az algoritmus azon a t´enyen alapul, hogy L1 = L2 akkor ´es csak akkor, ha L1 ⊆ L2 ´es L2 ⊆ L1 .)
Output: ”Igen”, ha L1 = L2 , k¨ ul¨onben ”Nem”.
139/141
140/141
Eld¨ont´esi k´erd´esek regul´aris nyelvekre ¨ Osszefoglal´ as K´ erd´ es Eleme-e ¨ Uress´ egi V´egtelen-e Tartalmaz´ as Ekvivalencia
Eld¨ onthet˝ o-e? igen igen igen igen igen
141/141
