1. előadás Matematikai és nyelvi alapok, Szintaktikai vizsgálat

Formális nyelvek

Széchenyi István Egyetem

1. előadás Matematikai és nyelvi alapok, Szintaktikai vizsgálat

Dr. Kallós Gábor

2014–2015 11

Formális nyelvek


Tartalom Matematikai alapfogalmak Halmazok Relációk Függvények Homomorfizmusok Számosságok, végtelenek

Nyelvi alapfogalmak Ábécé, szavak, nyelvek Műveletek szavakkal és nyelvekkel

Szintaktikai vizsgálat Kifejezés Köznapi nyelv Programozási nyelv

Nyelvek megadásának lehetőségei

2

Formális nyelvek


Matematikai alapfogalmak Halmazelmélet Halmaz és halmazhoz való hozzátartozás: nem definiált alapfogalom Tudjuk: a ∈ B és a ∉ B közül csak pontosan az egyik teljesül

Halmaz megadási módja Kapcsos zárójelben felsoroljuk az elemeit Megadjuk az elemeket jellemző tulajdonságo(ka)t (a módszer alkalmazhatóságát a részhalmaz axióma garantálja) { h | a h elem T tulajdonságú } Példa: { x ∈ R | 0 < x < 1}

A halmazelmélet (pontos matematikai) felépítése: axiómák, definíciók, állítások, tételek Meghatározottsági axióma Legyenek A és B halmazok. A akkor és csak akkor egyenlő B-vel, ha minden x ∈ A esetén x ∈ B, és minden y ∈ B esetén y ∈ A. Azaz: elemeik azonosak

Definíció Legyenek A és B halmazok. A része B-nek, ha minden x ∈ A-ra x ∈ B is teljesül (jelölés: A ⊂ B). Tétel (halmazok egyenlősége): A = B, ha A ⊂ B és B ⊂ A Üres halmaz axióma Létezik olyan halmaz, amelynek nincs eleme. Ez az üres halmaz, jelölése ∅. Állítás: Pontosan egy ilyen halmaz létezik 3

Formális nyelvek


Matematikai alapfogalmak Halmazelmélet (folyt.) Definíciók (Legyenek A és B halmazok) Unió, metszet, különbséghalmaz értelmezése (tudjuk) Jelölések: A∪B, A ∩ B, A \ B Az unió axiómából Disztributivitási tulajdonság, de Morgan azonosságok, egyéb összefüggések (igazolhatók)

A és B diszjunkt, ha nincs közös elemük Komplementer halmaz (H alaphalmazra vonatkozóan) H \ A, Jelölés: A

Hatványhalmaz axióma Legyen A halmaz. Létezik olyan halmaz, amely tartalmazza A minden egyes részhalmazát. Ezt a halmazt A hatványhalmazának nevezzük, P(A)-val jelöljük

Állítás: P(A) elemszáma 2|A| (ez indukcióval igazolható) Definíció: Legyenek A és B halmazok. A és B direkt (vagy Descartes-féle) szorzata az összes olyan rendezett (x, y) számpárból álló halmaz, amelyeknél x ∈ A és y ∈ B. A direkt szorzat jele: ×. A × B = {(x, y) | x ∈ A és y ∈ B} (Rendezett pár definíció) Általánosítható n darab halmazra

Feladat: Soroljuk fel A × B elemeit, ahol A = {1, 2} és B = {3, 4, 5} 4

Formális nyelvek


Matematikai alapfogalmak Relációk Definíció: Legyenek M1, M2, …, Mn tetszőleges halmazok. Egy ρ ⊆ M1 × M2 × … × Mn halmazt relációnak nevezünk (rendezett szám n-es) Megj.: Az üres halmaz is reláció (mert nincs olyan eleme, ami nem rendezett szám n-es)

Ha n = 2, akkor ρ-t bináris relációnak nevezzük Elemei rendezett párok, jelölés: 〈a, b〉 vagy (a, b) Itt már beszélhetünk értelmezési tartományról és értékkészletről (M1, ill. M2)

Legyen a ∈ A és b ∈ B egy ρ ⊆ A × B bináris reláció esetén. Ha ekkor 〈a, b〉 ∈ ρ teljesül, akkor azt mondjuk, hogy „a ρ relációban van b-vel”. Jelölések: ρ(a, b), vagy ρ〈a, b〉, vagy a ρ b. Definíció: Legyenek ρ ⊆ A × B1 és σ ⊆ B2 × C bináris relációk. Két bináris reláció kompozíciójának (szorzatának) nevezzük azt a ρ ◦ σ relációt, ahol ρ ◦ σ ⊆ A × C, és ρ ◦ σ = {〈a, c〉 | ∃ b ∈ B1 ∩ B2 úgy, hogy 〈a, b〉 ∈ ρ és 〈b, c〉 ∈ σ}. A kompozícióképzés nem kommutatív művelet Feladat: Legyen ρ = { 〈n, n + 1〉 | n ∈ N} és σ = { 〈n, 3n〉 | n ∈ N}. Adjuk meg a ρ ◦ σ és σ ◦ ρ relációkat!

Egy ρ ⊆ M × M reláció k-adik (k ≥ 0) hatványát a következő módon értelmezzük: ρ0 = { (a, a) | a ∈ M}; ρk + 1 = ρk ◦ ρ, ha k ≥ 1 Nyilván ρ1 = ρ 5

Formális nyelvek


Matematikai alapfogalmak Relációk (folyt.) Definíciók + 2 3 Egy ρ ⊆ M × M reláció tranzitív lezártja ρ = ρ U ρ U ρ U ... = Egy ρ ⊆ M × M reláció reflexív, tranzitív lezártja ρ* = ρ0 ∪ ρ+

∞

Uρ

k

k =1

ρ+ mindig tranzitív, és ez a legszűkebb olyan reláció, amely tranzitív, és tartalmazza ρ-t ρ* reflexív és tranzitív, és a legszűkebb az ilyen tulajdonságú ρ-t tartalmazó relációk közül

Definíció: Egy ρ ⊆ M × M (homogén) bináris reláció reflexív, ha minden x ∈ M-re fennáll x ρ x; szimmetrikus, ha minden x, y ∈ M-re x ρ y ⇒ y ρ x; antiszimmetrikus, ha minden x, y ∈ M-re x ρ y és y ρ x ⇒ x = y; tranzitív, ha minden x, y, z ∈ M-re x ρ y és y ρ z ⇒ x ρ z (Megj.: A homogén reláció meghatározása az, hogy értékkészlete része az értelmezési tartományának, de sokszor úgy használják, hogy a két halmaz megegyezik)

Speciális relációk Definíció: A ρ (homogén) bináris reláció ekvivalencia-reláció, ha reflexív, szimm. és tranzitív Ekvivalencia-reláció példák: egyenesek párhuzamossága, szakaszok egybevágósága, számhalmazok egyenlősége

Igazolható, hogy minden ekv.-reláció M-et páronként diszjunkt, nem üres részhalmazokra bontja fel (ekvivalencia-osztályok), és a részhalmazokból reprezentáns elem választható (Egy A halmazrendszer az A halmaz osztályfelbontása, ha A elemeinek uniója A-t adja, és tetszőleges két A-beli elemre teljesül, hogy ha nem diszjunktak, akkor megegyeznek) Reprezentáns példák: egyenesek párhuzamossága – irány fogalom; szakaszok egybevágósága – hosszúság fogalom

6

Formális nyelvek


Matematikai alapfogalmak Speciális relációk (folyt.) Definíció: A ρ (homogén) bináris reláció rendezési reláció, ha reflexív, antiszimmetrikus és tranzitív Ekkor (M, ρ)-t rendezett halmaznak nevezzük – olyan (rendezett) pár, amelynek első komponense egy nem üres halmaz, második komponense pedig egy, a halmazon értelmezett rendezési reláció Rendezett halmaz példák: (N N, ≤), és hasonlóan (Z Z, ≤), (Q Q, ≤), (R R, ≤); (P(H), ⊆) – ahol H tetszőleges halmaz, részhalmaz tulajdonsággal; (N N, | ), (Z Z, | ) – itt | az oszthatóság De: (N N, <) és (Z Z, <) nem rendezett halmaz, mert < nem reflexív!

Definíció: Egy f reláció függvény, ha minden 〈x, y〉 és 〈x, z〉 ∈ f esetén y = z Azaz: nincs két olyan eleme, hogy az első komp.ek megegyeznek, a másodikak pedig kül.ők Jelölések függvény esetén: f(a, b) vagy a f b helyett b = f(a)

Függvényekkel kapcsolatos fontos fogalmak (itt eml., összefoglaló módon, részl. nélkül) Értelmezési tartomány (Df), értékkészlet (Rf), leképezés, helyettesítési érték (x-hez hozzárendelt elem) Függvényképző eljárások: függvény leszűkítése, függvények kompozíciója, függvény invertálása (invertálható kell, hogy legyen a függvény) Képhalmaz, X ⊂ Df halmaz képe, Y ⊂ Rf halmaz ősképe

Legyen f: A → B. Azt mondjuk, hogy …

… f az A-t B-be leképező injekció, ha f invertálható; … f az A-t B-re leképező szuperjekció (szürjekció), ha Rf = B; … f az A és B közti bijekció, ha injekció és szuperjekció is 7

Formális nyelvek


Matematikai alapfogalmak Definíció: Az (A, F) párt algebrának nevezzük, ahol A nem üres halmaz, F pedig az A-n értelmezett műveletek halmaza Példák algebrákra: (N N, +), (N N, {+, ⋅})

Definíció: Legyen (A, ◦ ) és (B, •) két algebra. Egy h: A → B leképezést homomorfizmusnak nevezünk, ha … … injektív (monomorfizmus), azaz az értelmezési tartomány minden eleméhez az értékkészletnek pontosan egy eleme van hozzárendelve; … és művelettartó, azaz minden a, b ∈ A esetén érvényes, hogy h(a ◦ b) = h(a) • h(b). Ekkor A-t és h(A)-t homomorf(ak)nak nevezzük. A homomorfizmusok különös jelentősége az, hogy a definíciós halmaz struktúrájának típusát a képhalmazra viszik át (pl. csoportok) Egyes speciális struktúrák közötti homomorfizmusok (az algebrákon túl): csoportok, gyűrűk, vektorterek (köztük lineáris leképezések), rendezett halmazok

Ha a h: A → B függvény kölcsönösen egyértelmű (bijektív), és inverze is homomorfizmus, akkor izomorfizmusról beszélünk Az izomorf struktúrák algebrai nézőpont szerint megegyeznek Egyéb további speciális homomorfizmusok: Ha a leképezés szürjektív (epimorfizmus), illetve ha a leképzésnél B ⊂ A (endomorfizmus) (Homomorf és izomorf struktúrákkal részletesen foglalkozunk még a számtud. slide-okon is)

Félcsoport, monoid, csoport definíciója (számtud. slide-ok) 8

Formális nyelvek


Matematikai alapfogalmak Példa: az A I B = A U B de Morgan azonosság szemléltetése nyelvi környezetben Alaphalmaz: összes szó valamely ábécé felett, V* (lásd később) Legyen A a páros hosszú szavak halmaza, B a hárommal osztható hosszú szavak halmaza Ábra: A ∩ B, ill. A és B komplementerei, majd ezek uniója, …

9

Formális nyelvek


Matematikai alapfogalmak Számosságok, végtelenek Definíció: Ha két halmaz között létesíthető bijekció, akkor a két halmazt mennyiségileg egybevágónak (ekvivalensnek) nevezzük Ez a viszony is reflexív, szimmetrikus és tranzitív, jelölés (lehet): x

Számosság: Minden halmazhoz egyértelműen hozzárendelünk egy mérőszámot (elemek száma), oly módon, hogy a mennyiségileg egybevágó halmazok számossága ugyanaz, a nem egybevágóaké pedig különböző legyen Az üres halmaz számossága 0

Legyen n = {0, 1, 2, …, n – 1}. Ekkor n számossága n. Jelölés: n(n) = n vagy #n = n

Definíció: Egy H halmaz véges, és számossága n, ha van olyan n ∈ N, amelyre n x H Ha n ≠ m, akkor n és m mennyiségileg nem egybevágók

Ha egy H halmaz mennyiségileg egybevágó N-nel, akkor H-t megszámlálhatóan végtelen számosságúnak mondjuk Jelölés: n(N N) = a0

Igazolható, hogy P(N N) és R is végtelen halmaz, de mennyiségileg nem egybevágó N-nel. Az R-rel mennyiségileg egybevágó halmazok kontinuum (nem megszáml. végtelen) számosságúak. Feladatok Igazoljuk, hogy a természetes számok halmaza és a nemnegatív, páros számok halmaza mennyiségileg egybevágó! Lehet-e egybevágó N és a négyzetszámok halmaza?

Igazoljuk, hogy a valós számok [1, ∞) részhalmaza és a [0, 1) intervallum között létesíthető bijekció! *Mutassuk meg, hogy a [0, 1)-beli valós törtszámok halmaza nem felsorolható (nem megszámlálhatóak)! *El tudunk képzelni n(R R)-nél nagyobb számosságot? Hol jöhet ez elő?

10

Formális nyelvek


Nyelvi alapfogalmak Ábécé, szó Definíciók Ábécé: szimbólumok tetszőleges, nem üres, véges halmaza; jelölés: V (vagy Ʃ) A szimbólumokról (külön def. nélkül) feltesszük, hogy megkülönböztethetők és különböznek egymástól (Betűcsoport is választható szimbólumnak)

Szó (mondat): V elemeiből képzett sorozat, azaz a1…ak, ahol k ≥ 0, és a1, …, ak ∈ V Üresszó (null szó): k = 0 eset, jele λ (néha ε) Összes szó halmaza V felett (benne az üres szó is); jelölés: V* Ha az üresszót nem engedjük meg: V + = V* – {λ} (Megj.: Nem üres V halmaz esetén V* megszámlálhatóan végtelen)

Szó hossza (V felett): szimbólumok száma benne, jelölés: |w| (w szóra) Rekurzív definíció is lehetséges Itt |λ| = 0

Példa Legyen Ʃ = {a, b} Néhány szó Ʃ felett: a, b, ab, bb, baa, aba, abba, baba, … Hány szót tudunk felsorolni? Hány véges szót tudunk felsorolni? Szavak hossza Ʃ felett: |a| = 1, |ab| = 2, … Ʃ* = {λ, a, b, aa, ab, ba, bb, aaa, aab, aba, …} Milyen rendezést célszerű itt alkalmazni? Hány darab n hosszú szót tudunk megadni?

Feladat: Adjunk meg értelmes szavakat V = {if, then, else, a, b, c} felett 11

Formális nyelvek


Nyelvi alapfogalmak Ábécé, szó (folyt.) Példa: egy ábécé feletti összes szót kiíró program Elemzés Mikor áll le a program? (Mit is jelent a megszámlálhatóan végtelen?) Igaz-e, hogy bármely rögzített hosszú szó (pl. |w| = 1000) előbb-utóbb kiírásra kerül? Tudunk mondani olyan szót – az ábécé felett – amelyet nem ír ki a program? Milyen stratégiával lehetne kiíratni az i hosszú szavakat?

Feladatok Tervezzünk algoritmust (készítsünk programot), ami kiírja adott ábécé felett … … az összes páros hosszú szót! … az összes hárommal nem osztható hosszú szót! 12

Formális nyelvek


Nyelvi alapfogalmak Ábécé, szó (folyt.) Definíció Szavak egyenlősége: csak ha „betűről-betűre” megegyeznek, azaz valamely V*-beli p = a1…am és q = b1…bn szavakat pontosan akkor tekintünk egyenlőknek, ha m = n és ∀ i = 1, …, n-re ai = bi Tréfás példa Legyen V = {1, 2, +}. Ekkor V*-ban (persze nem matematikai értelemben…) fennáll, hogy 1+1 ≠ 2, mivel az 1+1 szó nem egyezik meg „betűről-betűre” a 2 szóval.

Definíció Szavak konkatenációja (egymás után írás, összefűzés, „szorzás”): u és v V*-beli szavakra uv ∈ V* Érvényes: |uv| = |u| + |v|

un: az u szó n-szer egymás után írva (hatványozás) Itt is megadható rekurzív definíció ∀ u ∈ V*-ra u0 = λ Igaz továbbá: xλ = λx = x

De: a konkatenáció általában nem kommutatív! (azaz általában uv ≠ vu) Példa Legyen Ʃ = {a, b}. Ekkor az abba Ʃ*-beli szó baba szóval való szorzata abbababa, ami nem egyezik meg a babaabba szóval.

13

Formális nyelvek


Nyelvi alapfogalmak Ábécé, szó (folyt.) Igazolható, hogy V* a konkatenáció művelettel egységelemes félcsoportot, monoidot alkot A művelet asszociatív, és az üresszó egység

Definíció Legyenek x és w V*-beli szavak. Azt mondjuk, hogy x prefixe (kezdőszelete) w-nek, ha van olyan y V*-beli szó, hogy w = xy. Ha x, y ≠ λ, akkor valódi prefixről beszélünk Valódi prefixre: |x| = k a prefix hossza Hasonlóan értelmezhető egy szó szuffixe (végződése)

Definíció Legyenek x és w V*-beli szavak. Azt mondjuk, hogy x részszava w-nek, ha van olyan y, z ∈ V*, hogy w = yxz (itt y és z lehet üresszó). Valódi részszó is hasonlóan értelmezhető Használatos az alszó, kezdő alszó, és befejező alszó megnevezés is

Feladat: Adjunk meg részszót, prefixet és szuffixet az abbababa szónál! Hány különböző prefix lehetséges?

Szó tükörképe is definiálható, jelölés: w–1 Igaz-e, hogy (uv)–1 = v–1u–1? 14

Formális nyelvek


Nyelvi alapfogalmak Ábécé, szó (folyt.) Definíció Legyen adott két ábécé, V és W. A V*-ot W*-ra képező függvényeket szófüggvényeknek nevezzük. Példák A már ismert w–1-et előállító „tükör” függvény, tükör(w) = w–1 A „fej” függvény, ahol fej(w) = w első betűje (1 hosszú valódi prefix), itt fej(λ) = λ

Definíció Legyen f : V* → W* szófüggvény. f hossztartó, ha |f(w)| = |w|. f kezdőszelettartó, ha f(uv) = f(u)w minden u, v ∈ V* esetén, valamilyen w ∈ W*-ra. Példák A „tükör” függvény hossztartó A „fej” függvény kezdőszelettartó

Feladat: Keressünk néhány további szófüggvényt, amelyek hossztartóak, ill. kezdőszelettartóak Elemi szóműveleteknek nevezzük azokat a szófüggvényeket, amelyek a jellegzetes gépelési hibákat korrigálják Egy betű beszúrása egy szóba, adott helyre Egy adott helyen lévő betű törlése egy szóból Egy adott helyen lévő betű másikra cserélése Két szomszédos betű felcserélése

15

Formális nyelvek


Nyelvi alapfogalmak Definíció Nyelv (vagy: V feletti nyelv, formális nyelv): V* tetszőleges L részhalmaza; azaz L ⊂ V* Adott formális elem adott nyelvbe való tartozása egyértelműen eldönthető Egy nyelv lehet üres, véges vagy végtelen Üres nyelv: L = ∅ Csak az üres szót tartalmazó nyelv: L = {λ} (ennek van egy eleme) Egyszerű alapnyelvek: L = {a} típusúak A véges nyelvek – elvileg – elemeik felsorolásával megadhatók

Teljes nyelv: L = V* (minden lehetséges szót tartalmaz)

Megjegyzések Egy adott véges, nem üres Ʃ ábécé feletti összes lehetséges nyelvek halmaza a Ʃ* összes részhalmazából alkotott halmaz, vagyis Ʃ* hatványhalmaza. Mivel Ʃ* számossága megszámlálhatóan végtelen, így Ʃ felett kontinuum sok (különböző) nyelv létezik. A hagyományos nyelvek (pl. magyar nyelv) nem tekinthetők „tiszta” formális nyelvnek: a nyelv „halmaza” nem „pontos”, nem véglegesen lezárt, ill. részben szubjektív is; továbbá ugyanazon szónak lehet több jelentése Feladat: Nézzünk meg különféle példákat a Word helyesírás ellenőrzőjében! Vegyük észre, hogy a rendszer egyes, köznapinak tekinthető szavakat nem ismer fel, máskor számunkra teljesen „magyartalan”, ismeretlen szavakat elfogad.

16

Formális nyelvek


Nyelvi alapfogalmak Példa: nyelvek V = {0, 1, …, 9} felett A magyar történelmi évszámok halmaza ekkor egy véges nyelv V felett Lehet persze szubjektív, de biztosan véges

A páratlan számok halmaza (tízes számrendszer) egy V feletti végtelen nyelv

Példa: néhány nyelv Ʃ = {a, b} felett Véges nyelvek L1 = {λ, a, aa, aab}, L2 = {x ∈ Ʃ* | |x| ≤ 7} Végtelen nyelvek L3 = {x ∈ Ʃ* | |x| páratlan}, L4 = {x ∈ Ʃ* | |x| prím} L5 = {λ, ab, aabb, aaabbb, …} = {anbn | n ≥ 0} L6 = {u ∈ {a, b}* | na(u) = nb(u)}

Feladat: Adjuk meg halmaz definícióval a következő nyelvet V = {a, b, c} felett: azon szavak, amelyek három vagy több a-val kezdődnek és utána csak 0 vagy több c-t tartalmaznak, illetve még azon szavak, amelyek egy vagy kettő a-val kezdődnek és utána csak 0 vagy több b-t tartalmaznak. Nyelvek megadásának lehetőségei Felsorolással, halmaz definícióval Döntési programmal (tdk. itt is szabályrdsz. van) Szabályokkal, generatív nyelvtannal (ez a legjobb eszköz, így lényegesen bonyolultabb nyelvek is hatékonyan megadhatók, lásd később) 17

Formális nyelvek


Műveletek nyelvekkel A nyelvek halmazok és jelsorozatok is egyben. Így a rajtuk értelmezett műveletek is kétféle típusúak. Boole műveletek (∪, ∩, \, ¯ ) Reguláris műveletek (+, •, *)

Tetszőleges L1, L2 ⊆ V* nyelvek esetén értelmezhető a nyelvek (mint halmazok) uniója, metszete, különbsége, illetve L1-nek a V*-ra vonatkozó komplementere, és ezek szintén V*-beliek A jelölések a megszokottak (∪, ∩, \, ¯ ) Egy formális definíció (a többi hasonlóan) L1 ∩ L2 = {p | p ∈ L1 és p ∈ L2 }

A komplementer képzésnél nagyon vigyázni kell az alaphalmaz megadására (!) Példa: Az L = {λ, a, aa, aab} nyelv komplementere teljesen más a Ʃ = {a, b}, illetve a Ʃ' = {a, b, c} felett

A konkatenációt is értelmezzük nyelvekre (ez a művelet halmazokra nincs értelmezve, itt a jelsorozat tulajdonság él!) L1L2 = {uv | u ∈ L1, v ∈ L2 } Általában L1 L2 ≠ L2 L1 Egy L1L2-beli szó nem feltétlenül csak egyféle módon bontható fel L1-beli és L2-beli elemekre

A konkatenáció segítségével egy nyelv önmagával vett konkatenáltját (szorzatát) is értelmezhetjük 18

Formális nyelvek


Műveletek nyelvekkel Nyelv i-edik hatványa Lk = LL…L Itt L0 = {λ} (megállapodás szerint), L1 = L Itt is lehetséges rekurzív definíció Ugyanúgy mint szavakra, használatos Vk = VV…V is (Az ábécé is nyelv, hiszen V ⊂ V*. Így az ábécére is értelmezett minden nyelvművelet, esetleg triviális eredménnyel.) ∞ Kleene-iteráció, a konkatenáció lezárása ∗ i L* = {λ} ∪ L ∪ LL ∪ LLL ∪ … (Kleene-csillag), vagy L = U L + = i 0 illetve: L = L ∪ LL ∪ LLL ∪ … (Kleene-plusz)

Azaz: az L*-beli elemek azok a jelsorozatok, amelyeket fel lehet úgy darabolni, hogy minden darab a nyelv mondata legyen (a darabok számára nincs megkötés) Itt L+ = L* is előfordulhat, pontosan akkor, ha λ ∈ L ∞ Hasonlóan: i ∗ V* = {λ} ∪ V ∪ VV ∪ VVV ∪ …, vagy V = V (Kérdés: Konzekvens ez az előző definícióval?) i =0

U

Természetes kérdés: zártak-e különböző nyelvosztályok ezekre a műveletekre? Az L nyelvosztály zárt a ◦ műveletre, ha tetszőleges L1, L2 ∈ L-re mindig L1 ◦ L2 ∈ L is teljesül (hasonlóan lehet egyváltozós műveletre is, Hf.) Később az ilyen típusú vizsgálatok fontosak lesznek

Egyéb érdekes művelet: nyelv megfordítása, L–1 = {w–1 | w ∈ L } 19

Formális nyelvek


Műveletek nyelvekkel Legyen V egy rögzített ábécé. Ekkor tetszőleges L, L1, L2, L3 ⊆ V* esetén érvényesek a következő összefüggések (D. P.): L1 ∪ L2 = L2 ∪ L1 (az unió kommutatív) (L1 ∪ L2) ∪ L3 = L1 ∪ (L2 ∪ L3) (az unió asszociatív) L ∪ L = L (az unió idempotens) L ∪ ∅ = ∅ ∪ L = L (az unióra nézve létezik egységelem, a ∅ üres nyelv) L1 ∩ L2 = L2 ∩ L1 (a metszet kommutatív) (L1 ∩ L2) ∩ L3 = L1 ∩ (L2 ∩ L3) (a metszet asszociatív) L ∩ L = L (a metszet idempotens) L ∩ V* = V* ∩ L = L (a metszetre nézve létezik egységelem, a V* univerzális nyelv) (L1L2)L3 = L1(L2L3) (a konkatenáció asszociatív) L{λ} = {λ}L = L (a konkatenációra nézve létezik egységelem, és ez {λ}) L ∅ = ∅ L = ∅ (a konkatenációra nézve létezik nullelem, és ez ∅; nem lehet szópárokat készíteni) L+ = LL* = L*L L* = L+ ∪ {λ} (L*)* = L* (az iteráció idempotens) (L+)+ = L+ (a + művelet idempotens) 20

Formális nyelvek


Műveletek nyelvekkel Nyelvekre vonatkozó összefüggések (folyt.) (L*)+ = (L+)* = L*

L1 = L1 (a komplementerképzés involúciós tulajdonságú)

Szemléltessük ezeket az összefüggéseket konkrét nyelv példákkal (fontosabb esetek)! Megjegyzések A műveletek asszociativitása miatt általában nem is szoktuk zárójelekkel jelezni a(z elméleti) sorrendjüket További zárójelek hagyhatók el az egyértelmű precedencia következtében, sorrend: az egyargumentumú műveletek (komplementer, Kleene-csillag és Kleene-plusz) precedenciája nagyobb, mint a kétargumentumúaké; a konkatenációé nagyobb, mint az unióé és metszeté Disztributivitási tulajdonságok is megfogalmazhatók

Feladat: hagyjuk el a felesleges zárójeleket a következő kifejezésekből, ill. hozzuk egyszerűbb alakra a kifejezéseket (L1*) ∩ L2, ((L1 ∪ L2) ∪ L3), (L*L), (L ∩ L) ∪ ∅ ∪( L ∪ L), L ∪ V*

Egyszerű nyelvműveleti példák {ab} ∪ {cd} = {ab, cd} {a, bx}{c, d} = {ac, ad, bxc, bxd}, {c, d}{a, bx} = {ca, da, cbx, dbx} {a, b}3 = {aaa, aab, aba, abb, baa, bab, bba, bbb} {ab}+ = {ab, abab, ababab, …}, {ab}* = {λ, ab, abab, ababab, …} Írjuk fel {a, bb}*-ot! 21

Formális nyelvek


Műveletek nyelvekkel Nyelvműveletek – feladatok (Főként D. P. 9–10.) Legyen V = {a, b, c}, L1 = {a, c, bb, aba}, L2 = {a, aba, abba, baba, abbaba, babaabba}. Adjuk meg az L1 ∪ L2, L1 ∩ L2, L1 L2, L1 L1 halmazokat. Legyen T = {a, b}, L1 = {anbn | n ≥ 0}, L2 = {a2n+1b | n ≥ 0} L3 = {a2n | n ≥ 0}. Adjuk meg az L1 ∪ L2, L1 ∩ L2, L1 L2, L2 ∩ L3, L1 ∩ L3, (L2)* halmazokat. Adjunk példát olyan V ábécé feletti L1 és L2 nyelvekre, amelyekre L1 L2 = L2 L1. (Próbáljunk nem triviális megoldást is megadni.) Adottak L1 és L2 véges nyelvek V ábécé felett úgy, hogy | L1 | = n és | L2 | = m. Mennyi lehet a számossága az L1 ∪ L2, L1 ∩ L2 és L1 L2 nyelveknek? Adjunk meg alsó és felső korlátot, továbbá példákat is. Igazoljuk vagy cáfoljuk, hogy (L1 ∪ L2)* = (L1)* ∪ (L2)* Segítség: az állítás hamis, például L1 = {a}, L2 = {b}-re látható

Mivel egyenlő L2, ha L = {anbn | n > 0} 22

Formális nyelvek


Nyelvek megadása döntési programmal Döntési program (nyelvhez tartozóan): válaszol arra a kérdésre, hogy egy adott szó eleme-e a nyelvnek A döntési program a fordító része

Illusztrációs példa a V = {a, b} feletti Lp = {aibj | i ≥ 3, j ≥ 0} ∪ {ai | 1 ≤ i ≤ 2} nyelvhez (A. P.) Cél (később): a döntési program könnyen generálható legyen (automaták segítségével)

23

Formális nyelvek


Szintaktikai vizsgálat Példa: Egy aritmetikai kifejezés szintaxisának megadása (bevezető a generatív nyelvtanhoz) (Minden programozási nyelvben előfordul) Adott egy rögzített elemekből felépített kifejezés. Feladatunk eldönteni, hogy szintaktikusan helyes-e (nem „ránézésre” vagy „megérzéssel”, hanem algoritmussal). Ehhez formalizálni kell a rendszert! Milyen szimbólumok, számok, műveleti jelek szerepelhetnek a kifejezésben? Rögzítünk egy megfelelő halmazt (ebben az egyszerű példában): változók (A, B, C), konstansok (0, 1), műveleti jelek (+, ∗) és zárójelek Példa kifejezések: A + B ∗ C, AB ++ (C∗)

Milyen szabályok alapján épülhet fel a kifejezés a már rögzített szimbólumokból? Rekurzív definíció: a kifejezés állhat egy tagból, vagy lehet több tag összege; azaz a kifejezés lehet egy kifejezés és egy tag összege Nyilván definiálni kell majd a tagot is (és a többi részegységet is) Tömör és egyértelmű megfogalmazás kell!

Formális leírás elemei kifejezés = 〈kif.〉, tag = 〈tag〉, vagy művelet = |, „lehet” = → (vagy: ::=, Backus–Naur jelölés)

Kifejezés definíciója Így tehát 〈kif.〉 → 〈tag〉 | 〈kif.〉 + 〈tag〉 24

Formális nyelvek


Szintaktikai vizsgálat Példa: Egy aritmetikai kifejezés szintaxisának megadása (folyt.) Tag definíciója Lehet egy tényezőből álló szorzat (faktor), vagy több tényező szorzata (szintén rekurzív definícióval) 〈tag〉 → 〈fakt.〉 | 〈 fakt.〉 ∗ 〈fakt.〉

Faktor definíciója Lehet egy zárójelbe tett kifejezés, vagy változó, vagy konstans 〈fakt.〉 → (〈kif.〉) | 〈vált.〉 | 〈konst.〉 A kifejezésből kaphatunk majd újra tagot Itt teljes zárójelezést használunk, ami esetleg egyébként elhagyható lenne, de ezt nem tudjuk könnyen formalizálni – a prioritás kezelésére: lengyel-forma vagy valami hasonló eszköz kellene

Változók és konstansok (ebben a példában)



〈vált.〉 → A | B | C 〈konst.〉 → 0 | 1

Azaz: aritmetikai kifejezésnek az A, B, és C változó jelekből, a 0 és 1 konstans jelekből, a + és ∗ műveleti jelekből a „(” és „)” csoportosító jelekből a 〈kif.〉 → 〈tag〉 | 〈kif.〉 + 〈tag〉 〈tag〉 → 〈fakt.〉 | 〈 fakt.〉 ∗ 〈fakt.〉 〈fakt.〉 → (〈kif.〉) | 〈vált.〉 | 〈konst.〉 〈vált.〉 → A | B | C 〈konst.〉 → 0 | 1

… szabályok alkalmazásával felépíthető jelsorozatokat (szavakat/mondatokat) nevezzük

25

Formális nyelvek


Szintaktikai vizsgálat Példa: Egy aritmetikai kifejezés szintaxisának megadása (folyt.) Hogyan építhető fel egy szó a fenti szabályok alkalmazásával? 〈kif.〉-ből indulunk Egy jelsorozat (szó) esetén helyettesítsük a részegységek megnevezésére szolgáló szimbólumot az őt definiáló szintaktikai szabály jobb oldalának valamely lehetséges változatával (alternatíva) Helyettesítés (jelölés): ⇒

A ∗ (B + 1) levezetése 〈kif.〉 ⇒ 〈tag〉 ⇒ 〈 fakt.〉 ∗ 〈fakt.〉 ⇒ 〈 fakt.〉 ∗ (〈kif.〉) ⇒ 〈 fakt.〉 ∗ (〈kif.〉 + 〈tag〉) ⇒ 〈fakt.〉 ∗ (〈tag〉 + 〈tag〉) ⇒ … ⇒ 〈fakt.〉 ∗ (〈fakt.〉 + 〈fakt.〉) ⇒ 〈vált.〉 ∗ (〈fakt.〉 + 〈fakt.〉) ⇒ … ⇒ 〈vált.〉 ∗ (〈vált.〉 + 〈konst.〉) ⇒ A ∗ (〈vált.〉 + 〈konst.〉) ⇒ … ⇒ A ∗ (B + 1) Szintaktikailag hibás kifejezést nem tudunk így levezetni, például: + ∗ (B + 1), )B + 1(

Ilyen következtetési mód: levezetés Persze a gyakorlatban bonyolultabb aritmetikai kifejezések jönnek elő (ez a példa nagyon egyszerű), de azok is ugyanilyen módon kezelhetők

Szintaxis ezen megadási módja: generatív nyelvtannal való szintaxis megadás (Ez a leggyakoribb) 26

Formális nyelvek


Szintaktikai vizsgálat és generatív nyelvtanok (Eddigi tapasztalataink alapján…) Mit kell tartalmaznia egy generatív nyelvtan definíciójának? Azon szimbólumok (betűk) megadását, amelyekből a nyelvtannal definiálandó nyelv szavai állhatnak (terminális szimbólumok, nyelvi szimbólumok) Azon további szimbólumok megadását, amelyek nem szerepelnek (!) a nyelv szavaiban (mondataiban), de szükség van rájuk a szintaktikai szabályok megfogalmazásához (nemterminális szimbólumok, grammatikai szimbólumok) A szintaktikai (levezetési) szabályokat Azt a nemterminális szimbólumot (kezdő szimbólum), amelyből levezetés alkalmazásával a definiálandó nyelv valamennyi szavát megkapjuk A levezetés pontos definícióját

A levezetés során lesznek Tiszta terminális szavak (tiszta nyelvi szavak, „mondatok”) Vegyes, terminális és nemterminális jeleket tartalmazó szavak („mondatformák”)

Szokásos jelölés szimbólum = terminális szimbólum (nem mindig dőlten írva) 〈szimbólum〉 = nemterminális szimbólum

A nyelv szavait mind le kell tudni vezetnünk, de csak pontosan azokat (!) 27

Formális nyelvek


Szintaktikai vizsgálat Példa: Köznapi nyelv (leszűkített részhalmaz, „minimagyar”; B. I.) Szabályok 〈mondat〉 ::= 〈alanyi rész〉 〈állítmányi rész〉 〈alanyi rész〉 ::= 〈főnévi rész〉 〈határozó〉 〈állítmányi rész〉 ::= 〈tárgyi rész〉 〈igei rész〉 〈főnévi rész〉 ::= 〈névelő〉 〈jelzők〉 〈főnév〉 〈jelzők〉 ::= 〈jelző〉 | 〈jelző〉 〈jelzők〉 〈tárgyi rész〉 ::= 〈főnévi rész〉t 〈névelő〉 ::= λ | a | az | egy 〈jelző〉 ::= λ | hideg | meleg | fehér | fekete | nagy | kis 〈főnév〉 ::= kutya | macska | hús | egér | sajt | tej | víz 〈határozó〉 ::= λ | nappal | éjjel | reggel | este 〈igei rész〉 ::= eszik | iszik

Megjegyzések A szavak itt terminális szimbólumok (de most nem dőlten írtuk őket) A mondat végére írhatnánk pontot (de ekkor is gond lenne abból, hogy a nagybetűs kezdést nem tudnánk egyszerűen biztosítani Látható már most is, hogy nem tudunk minden valós nyelvtani szabályt alkalmazni (tárgyi rész: sajt, sajtot, víz, vizet, tej, tejet) 28

Formális nyelvek


Szintaktikai vizsgálat Példa: „Minimagyar” (folyt.) Levezetés példa 〈mondat〉 ⇒ 〈alanyi rész〉 〈állítmányi rész〉 ⇒ 〈főnévi rész〉 〈határozó〉 〈állítmányi rész〉 ⇒ 〈névelő〉 〈jelzők〉 〈főnév〉 〈határozó〉 〈állítmányi rész〉 ⇒ a 〈jelzők〉 〈főnév〉 〈határozó〉 〈állítmányi rész〉 ⇒ a 〈jelző〉 〈jelzők〉 〈főnév〉 〈határozó〉 〈állítmányi rész〉 ⇒ … a nagy fehér 〈főnév〉 〈határozó〉 〈állítmányi rész〉 ⇒ a nagy fehér kutya 〈határozó〉 〈állítmányi rész〉 ⇒ a nagy fehér kutya reggel 〈állítmányi rész〉 ⇒ a nagy fehér kutya reggel 〈tárgyi rész〉 〈igei rész〉 ⇒ a nagy fehér kutya reggel 〈főnévi rész〉t 〈igei rész〉 ⇒ a nagy fehér kutya reggel 〈névelő〉 〈jelzők〉 〈főnév〉t 〈igei rész〉 ⇒ … a nagy fehér kutya reggel 〈jelző〉 〈főnév〉t 〈igei rész〉 ⇒ … a nagy fehér kutya reggel meleg húst 〈igei rész〉 ⇒ a nagy fehér kutya reggel meleg húst eszik

Ez normális magyar mondat, de persze sok – a mi szintaktikánk szerint helyes – „normális magyarul” mégis szintaktikailag hibás mondatot is le tudunk így vezetni „az fehér egér hideg sajtt eszik” „az kis fekete macska meleg tejt iszik”

Hasonlóan levezethető több, „normális magyarul” szemantikailag is támadható mondat „a fehér tej macskat iszik”

És persze léteznek „minimagyarul” is szintaktikailag helytelen (levezethetetlen) mondatok „hús kutya reggel fekete eszik víz az”

29

Formális nyelvek


Szintaktikai vizsgálat Példa: Egy programozási nyelv szintaxisának megadása (F. Z.) Szándékosan egyszerű programozási nyelvet választunk (PÉLDA) Kezdőszimbólum: 〈program〉

Szabályok 〈program〉 → 〈ut. lista〉. 〈ut. lista〉 → 〈ut.〉 | 〈ut.〉; 〈ut. lista〉 〈ut.〉 → 〈ért. adó〉 | 〈if ut.〉 | 〈while ut.〉 | 〈blokk〉 〈ért. adó〉 → 〈vált〉 := 〈kif.〉 〈if ut.〉 → if 〈reláció〉 then 〈ut.〉 else 〈ut.〉 〈while ut.〉 → while 〈reláció〉 do 〈ut.〉 〈blokk〉 → begin 〈ut. lista〉 end 〈reláció〉 → 〈kif.〉 〈relációjel〉 〈kif.〉 〈relációjel〉 → < | > | = | ≠ 〈kif.〉 → 〈tag〉 | 〈kif.〉 + 〈tag〉 〈tag〉 → 〈fakt.〉 | 〈 fakt.〉 ∗ 〈fakt.〉 〈fakt.〉 → (〈kif.〉) | 〈vált.〉 | 〈konst.〉 〈vált.〉 → A | B | C 〈konst.〉 → 0 | 1

Egy jelsorozat akkor és csak akkor szintaktikusan helyes PÉLDA nyelvű program, ha levezethető a 〈program〉 nemterminális szimbólumból a fenti szabályok alkalmazásával Feladat: Adjunk meg szintaktikusan helyes és helytelen PÉLDA nyelvű programot! 30

Formális nyelvek


Szintaktikai vizsgálat Egyszerű programok esetében (viszonylag) könnyű eldönteni, hogy szintaktikusan helyesek-e [A szintaktikusan helyesnek bizonyult kódokat utána még természetesen szemantikusan is elemezni kell! (Ezzel egyelőre nem foglalkozunk.) Időnként beépítenek bizonyos szemantikai ellenőrzést a szintaktikába, pl. szám és – szám típusú – szöveg összeadása, Excelben megengedett, C-ben/Java-ban nem Beadható feladat: Készítsünk szintaktikailag helyes, de szemantikailag helytelen kódot Cben, Java-ban Ugyanakkor még a szemantikai helyesség sem garantálja feltétlenül az értelmes/céljainknak megfelelő működést]

Probléma hosszú programoknál

 A levezetés során sok konfliktus adódik (több lehetőség a helyettesítésre, melyik a jó/melyiket válasszuk?) Intuitív módon: Az a cél, hogy közelebb kerüljünk a kívánt végeredményhez Algoritmikusan: Valami módon sorba rakjuk a szabályokat, ebben a sorrendben alkalmazzuk őket a helyettesítésnél Lehet, hogy rossz szabályt választottunk! (Backtrack technikákat is be kell vetni, ez viszont magával vonja a rekurzív működést és az exponenciális típusú kimenetelt…)

Mennyi sikertelen levezetési kísérlet után lehet kimondani, hogy a program szintaktikusan helytelen?

Ezekre a (nehéz) kérdésekre választ adnak az elemzési algoritmusok A jó elemzési algoritmus legfeljebb az input hosszának konstansszorosa számú lépést hajt végre, és utána megadja a választ 31

Formális nyelvek


Nyelvek megadása egyéb szabályrendszerrel Szintaxis gráf/diagram Cél: Annak bemutatása, hogy hogyan kell szintaktikusan helyes programot írni egy adott nyelven Minden programozási nyelv mögött áll egy ilyen struktúra Sokan nem nézik meg (ill. nem is tudnak róla) Gyakorlott programozók számára is hasznos lehet (ritkán használt elemek)

A szintaktikailag helyes Pascal-nyelvű program felső szintű megadása: Értelmezzük a gráfot (rekurzív struktúra)!

Ezen belül az azonosító megadása: Feladat Tekintsük a következő programrészletet: program szamol(be, ki, file); Hogyan feleltethetőek meg az egyes elemek a szintaxis gráf elemeinek? Ha a betű és a számjegy nem lenne terminális, akkor hogyan tudnánk definiálni? *Próbáljuk meg kifejteni a blokkot! (ld. 30. slide)

Megj. (tudjuk): a szintaktikai szabályrendszer még nem mondja meg azt, hogy hogyan kell szemantikailag helyes programot írni 32

Formális nyelvek


Nyelvek megadása egyéb szabályrendszerrel Backus–Naur jelölés Metanyelv, szintén egy adott nyelv szintaxisát írja le (alternatíva a gráf mellett) Eredetileg az ALGOL 60 nyelvhez készítették el, népszerűvé vált és elterjedt A Pascal nyelvet teljesen így definiálták (1975)

Elemei a szintaxis gráf elemeinek egyértelműen megfeleltethetők Terminális (ellipszis, kör vs. sima szöveg) Nemterminális v. fogalom (téglalap vs. 〈 〉 közötti megadás) Felbontás, kifejtés (kifejtés vs. ::=) Konkatenáció (nyíl vs. egymás mellé írás) Alternatíva (elágazás vs. | ) Iteráció (visszanyíl vs. { }) Opció – fakultatív megjelenés (fordított iterációval vs. [ ])

BNF (Extended BNF, az iteráció miatt) megadás az előző programra:

Milyen terminális elemeket találunk a példában? 33

Formális nyelvek


Nyelvek megadása egyéb szabályrendszerrel Példa a Backus–Naur jelölés alkalmazására (azonosító leírása) Szabályok 〈azonosító〉 ::= 〈betű〉 〈azonosító〉 ::= 〈betű〉 〈azonosítóvég〉 〈azonosítóvég〉 ::= 〈betű〉 〈azonosítóvég〉 ::= 〈számjegy〉 〈azonosítóvég〉 ::= 〈betű〉 〈azonosítóvég〉 〈azonosítóvég〉 ::= 〈számjegy〉 〈azonosítóvég〉 〈betű〉 ::= a … 〈betű〉 ::= z 〈számjegy〉 ::= 0 … 〈számjegy〉 ::= 9

Ugyanez alternatívákkal, iterációval 〈azonosító〉 ::= 〈betű〉 | 〈betű〉 〈azonosítóvég〉 〈azonosító〉 ::= 〈betű〉 { | 〈azonosítóvég〉 } 〈azonosítóvég〉 ::= 〈betű〉 | 〈számjegy〉 | 〈betű〉 〈azonosítóvég〉 | 〈számjegy〉 〈azonosítóvég〉 〈azonosítóvég〉 ::= { 〈betű〉 | 〈számjegy〉 } { | 〈azonosítóvég〉 } 〈betű〉 ::= a | b | … | z 〈számjegy〉 ::= 0 | 1 | … | 9

Feladatok Vezessük le a szabályok alkalmazásával az a12 és az alma azonosítókat! Módosítsuk a szabályokat úgy, hogy egyéb karakterek is alkalmazhatók legyenek (pl. _) Építsünk fel szabályrendszert az egész számok és a valós számok leírására!

Külön köszönet: a hivatkozott jegyzetek szerzőinek

34

Formális nyelvek


Ajánlott irodalom Fülöp Zoltán: Formális nyelvek és szintaktikus elemzésük, Polygon, Szeged, 2001 Dömösi Pál és társai: Formális nyelvek és automaták, Elektronikus jegyzet, 2011 Bach Iván: Formális nyelvek, Typotex kiadó, Budapest, 2002 Alan P. Parkes: A Concise Introduction to Languages and Machines, Springer, London, 2008 Katona Gyula, Recski András, SzabóCsaba: A számítástudomány alapjai, Typotex Kiadó, Budapest, 2003 Tichler Károly: Oktatási segédanyagok (gyakorlatok) a formális nyelvek tárgyhoz, ELTE, Budapest, 2008 Várterész Magda: Oktatási segédanyagok (előadások) a formális nyelvek és automaták tárgyhoz, DE, Debrecen, 2006

35

1. előadás Matematikai és nyelvi alapok, Szintaktikai vizsgálat

Recommend Documents