Automaták és formális nyelvek

Automaták és formális nyelvek Bevezetés a számítástudomány alapjaiba 1. Formális nyelvek 2006.11.13.

1

Automaták és formális nyelvek - bevezetés • Automaták elmélete: információs gépek általános absztrakt matematikai modelljei • Információs gépek: • bemenő adat: információ a környezettől • kimenő adat: információ a környezet felé • Kalman-féle rendszer modellbe illeszthetőség

Formális nyelvek/2

Automaták és formális nyelvek - bevezetés • Formális nyelvek: • információ feldolgozás alapeszközei • adathalmazok: véges sok jelből alkotott szavak • szavak halmaza: nyelv • nyelv: szabályok a szavak alkotására, feldolgozására

Formális nyelvek/3

Formális nyelvek - alapfogalmak • Def.: Ábécé Szimbólumok (jelek) tetszőleges, nemüres, véges halmazát ábécének, az ábécét alkotó jeleket betűknek nevezzük. • jel: alapfogalom • ábécék halmazok, így alkalmazhatók rájuk a halmazműveletek

Formális nyelvek/4

Formális nyelvek - alapfogalmak • Def.: Szó Legyen adott egy tetszőleges ábécé. Ekkor az ábécé betűiből alkotott véges sorozatokat szavaknak, az adott ábécéből alkotott szavaknak nevezzük. • Pl.: V = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} ábécéből származó szavak a tízes számrendszerben felírt számok.

Formális nyelvek/5

Formális nyelvek - alapfogalmak • Def.: Szó hossza A szó hossza alatt a szót alkotó jelek számát értjük. Jele: α szó hossza d(α) • Def.: Üres szó Az egyetlen betűt sem tartalmazó sorozatot üres szónak nevezzük és ε-nal jelöljük. Természetesen d(ε)=0.

Formális nyelvek/6

Formális nyelvek - alapfogalmak • Def.: Szavak egyenlősége Két szó egyenlő, ha hosszuk megegyezik és a betűik páronként rendre megegyeznek. Legyen α és β két szó. α = β, ha d(α) = d(β) = n és a1 = b1, a2 = b2, …, an = bn.

Formális nyelvek/7

Formális nyelvek - alapfogalmak • Példa: • Legyen V1 = {0, 1} ábécé szavai: ε , 110100 , 00 hosszuk: 0 , 6, 2. • Legyen V2 = {if, then else, for to, do, begin, a, b, c} szavai: if a then b else c , for b to c do begin a hosszuk: 6, 7

Formális nyelvek/8

Formális nyelvek - alapfogalmak • Def.: Szavak szorzása Legyen α és β két szó. α és β szorzatán (egyesítésén) azt az új szót értjük, ami úgy jön létre, hogy β-t leírjuk az α után. Az így kapott új szót az αβ jelöli. • Ha α = a1a2…an és β = b1b2…bm, akkor αβ = a1a2…an b1b2…bm • ha α ∈V és β∈W, akkor αβ∈V∪W • d(αβ) = d(α)+d(β) azaz d(αβ) = n+m Formális nyelvek/9

Formális nyelvek - alapfogalmak • tetszőleges szóra igaz: εα = αε = α • szavak szorzása asszociatív, de nem kommutatív • Példa

Formális nyelvek/10

Formális nyelvek - alapfogalmak • Def.: Szavak hatványozása Ha α egy tetszőleges szó, akkor α0 = ε, α1 = α, illetve αn = αn-1α, n=1, 2, 3, … esetén. • Def.: Szó tükörképe A szó tükörképének azt α-1-gyel jelölt szót nevezzük, amely az α betűit fordított sorrendben tartalmazza, azaz α=a1a2…an esetén α-1 =anan-1…a1.


Formális nyelvek - alapfogalmak • Def.: Szó kezdőszelete, végszelete, részszava • Az α szó a β szónak kezdőszelete (prefixuma), ha létezik olyan γ szó, amelyre β = αγ. • Az α szó a β szónak végszelete (szuffixuma), ha létezik olyan γ szó, amelyre β = γα. • Az α szó a β szónak részszava, ha léteznek olyan µ és η szavak, amelyre β = µαη. • Ha V egy tetszőleges ábécé, akkor a V-ből alkotott összes szavak halmazát jelöljük V*-gal. Formális nyelvek/12

Formális nyelvek - alapfogalmak • Def.: Formális nyelvek Egy adott ábécéből alkotott szavak tetszőleges halmazát formális nyelvnek nevezzük. Másképpen egy L halmazt pontosan akkor nevezünk formális nyelvnek, létezik olyan VL ábécé, melyre L ⊆ VL*.


Formális nyelvek - alapfogalmak •

Példa: Legyen V={0, 1} ábécé, ekkor a V-ből alkotott formális nyelvek: • az üres halmaz ∅; • az üres szót tartalmazó egy elemű halmaz {ε}; • a V*; • L1 ={0, 00, 010, 1100} ; • L2 ={0n1n : n ≥ 0} ; Formális nyelvek/14

Formális nyelvek - alapfogalmak •

az L3 halmaz, amelyet az alábbiak szerint határozunk meg: 1. ε ∈ L3; 2. ha α ∈ L3, akkor 0α1 ∈ L3 és 1α 0 ∈ L3 ; 3. ha α ∈ L3 és β ∈ L3 akkor α β ∈ L3 ; 4. L3 -ben nincs más szó, csak azok, amik az 1.-3. szabályok véges sokszori alkalmazásával megkaphatunk.

•

véges – végtelen nyelvek Formális nyelvek/15

Formális nyelvek - alapfogalmak • Műveletek nyelvekkel: • Halmazelméleti műveletek • L1 ∪ L2 = {ω : ω ∈ L1 vagy ω ∈ L2} • L1 ∩ L2 = {ω : ω ∈ L1 és ω ∈ L2} • L1 - L2 = {ω : ω ∈ L1 és ω ∉ L2} • L = V*-L, ahol V az L-hez tartozó ábécé.


Formális nyelvek - alapfogalmak • Def.: Formális nyelvek szorzása Legyen adott két nyelv L1 és L2, a hozzájuk tartozó ábécék pedig legyenek W1 és W2. Az L1 és L2 nyelvek L1⋅L2 szorzatán a következő W1∪W2–ből alkotott nyelvet érjük: L1⋅L2 = {αβ : α ∈ L1 és β ∈ L2} • Példa L1 = {0, 01}, L2 = {1, 11} akkor L1⋅L2 = {01, 011, 0111} • A szorzás ebben az esetben is asszociatív, de /17 nem kommutatív. Formális nyelvek

Formális nyelvek - alapfogalmak • Def.: Formális nyelvek hatványozása Legyen L tetszőleges nyelv, V pedig a hozzá tartozó ábécé. Az L nyelv hatványait a következő módon határozzuk meg: L 0 = {ε } L1 = L Ln = Ln-1⋅ L, n = 1, 2, 3, … • Példa: Legyen L = {0, 1} Ekkor: L2 = L⋅L = {00, 01, 10, 11} L3 = L2⋅L = {000, 010, 100, 110, 001, 011, 101, 111}


Formális nyelvek - alapfogalmak • Def.: Formális nyelv iteráltja Az L nyelv hatványainak egyesítését az L nyelv iteráltjának nevezzük L*-gal jelöljük: L∗ = U Ln n≥0

• L iteráltja tehát az L-beli szavak tetszőleges véges sok tényezőiből álló szorzatainak a halmaza.


Formális nyelvek - alapfogalmak • Példa: Legyen L = {0, 01} Ekkor: L2 = L⋅L = {00, 001, 010, 0101} L3 = L2⋅L = {000, 0010, 0100, 01010, 0001, 00101, 01001, 010101} és az iterált L* = {0, 01, 00, 001, 010, 0101, 000, 0010, 0100, …}


Formális nyelvek - Grammatikák • Generatív grammatikák: • élő nyelv: szavak sorozatáról a nyelvtan szabályai alapján döntjük el, hogy mondat-e • formális nyelvek: • szavak generálása • struktúra hozzárendelése • információ a matematikai informatika, programozási nyelvek, gépi fordítóprogramok, számítási módszerek modellezése Formális nyelvek/21

Formális nyelvek - Grammatikák • Generatív grammatika elemei: • Egy ábécé, melynek az elemei a terminális jelek. Ez az ábécé a grammatika kimenő ábécéje, mely a generált nyelvhez tartozik. • Egy másik ábécé, melynek az elemei a nemterminális jelek. Ez egy segédeszköz, betűi nem szerepelnek a generált nyelv szavaiban. • Egy kezdő szimbólum (rögzített nemterminális jel). Formális nyelvek/22

Formális nyelvek - Grammatikák • A szavak alkotását megadó helyettesítési szabályok. Ezek terminális és nemterminális jelekből alkotott szavak rendezett párjai, melyekben az első tag legalább egy nemterminális jelet tartalmaz.


Formális nyelvek - Grammatikák • Generálás folyamata • kiindulunk a egy szóból, amely kezdetben egyetlen jelből, a kezdőszimbólumból áll; • ezután a vizsgált szó valamelyik részszavát egy alkalmazható helyettesítési szabály alapján egy másik szóra cseréljük ki; • az eljárás addig folytatjuk, amíg olyan szóhoz nem jutunk, amely csak terminális jelekből áll; • a kapott szó eleme lesz a generált nyelvnek. Formális nyelvek/24

Formális nyelvek - Grammatikák • Def.: Generatív grammatika Egy G generatív grammatikán a következő rendezett négyest értjük: G = ahol V – a terminális jelekből álló ábécé; W – a nemterminális jelekből álló ábécé; S ∈ W – a kezdőszimbólum; P = {< α, β >} – szabályhalmaz. Formális nyelvek/25

Formális nyelvek - Grammatikák • P olyan < α, β > rendezett pároknak a véges halmaza, melyeknél α és β a V∪W halmazból alkotott szavak, és α-nak legalább egy betűje nemterminális jel. • P elemeit helyettesítési szabályoknak nevezzük, jelölési mód: α → β azaz α szó helyettesíthető β szóval.


Formális nyelvek - Grammatikák • Def.: Közvetlen levezethetőség A G = grammatika alapján a µ szó közvetlenül levezethető az η szóból, ha µ,η ∈ (V ∪ W)*, és léteznek olyan γ,δ ∈(V ∪ W)* szavak, valamint olyan α → β szabály P-ben, amelyekre η = γαδ , µ = γβδ jelölése: η µ


Formális nyelvek - Grammatikák • Def.: Levezethetőség Szavaknak egy ω1, ω 2,… ωn sorozatára azt mondjuk, hogy ez ωn–nek ω1–ből történő levezetése a G grammatika alapján, ha ω1 ω2 ωn . … Ha létezik ez a levezetés akkor azt mondjuk, hogy ωn levezethető ω1–ből a G grammatika alapján és a következőképpen jelöljük:

ω1

ωn

A közvetlen levezetések száma adja meg a levezetés hosszát.


Formális nyelvek - Grammatikák • A G = grammatika generálja az α szót, ha α ∈ V*-nak és α levezethető S-ből, azaz S α. • Azt mondjuk, hogy a G = grammatika generálja az L ⊆V* nyelvet, ha α} L = {α : α ∈ V*, S Ebben az esetben L-re használjuk az L(G) jelölést.


Formális nyelvek - Grammatikák • Két grammatikát, G’-t és G”-t akkor nevezünk ekvivalensnek, ha L(G’)=L(G”). • Példa


Formális nyelvek - Grammatikák • Tétel Legyen adva egy G= generatív grammatika és tegyük fel, hogy P-ben vannak olyan szabályok, amelyek a jobb oldali szavukban is tartalmazzák az S kezdőszimbólumot. Ekkor meg lehet adni olyan G’ grammatikát, amely ekvivalens lesz G-vel, és amelyben a helyettesítési szabályok jobb oldalán nem fordul elő a G’ kezdőszimbóluma.


Formális nyelvek – Grammatikák csoportosítása • Grammatikák csoportosítása : a helyettesítési szabályokra tett megkötések alapján 1. csoport: Az olyan generatív grammatikákat, amelyeknek a helyettesítési szabályaira semmiféle megszorítást nem teszünk, vagyis amelyekben a szabályok: αAβ → ω alakúak, ahol α,β és ω terminális és nemterminális jelekből alkotott szavak, A pedig nemterminális jel, általános vagy 0-típusú grammatikáknak nevezzük. /32 Formális nyelvek

Formális nyelvek – Grammatikák csoportosítása 2. csoport: Azokat a G = generatív grammatikákat, amelyeknek a helyettesítési szabályai: αAβ → αωβ alakúak, ahol α,β,ω∈(V∪W)*, ω ≠ε és A∈W, környezetfüggő vagy 1-típusú grammatikáknak nevezzük. • Ilyen szabályok esetén az A szimbólum csak αβ környezet esetén helyettesíthető az ω szóval. • Példa


Formális nyelvek – Grammatikák csoportosítása 3. csoport: Azokat a G= generatív grammatikákat, amelyeknek a helyettesítési szabályai: A→ ω alakúak, ahol A∈W, ω∈(V ∪ W)* és ω ≠ ε, környezetfüggetlen vagy 2-típusú grammatikáknak nevezzük. • Példa


Formális nyelvek – Grammatikák csoportosítása 4. csoport: Azokat a G= generatív grammatikákat, amelyeknek minden helyettesítési szabálya: A → aB vagy A → a alakú, ahol A, B∈W, a ∈ V, reguláris vagy 3típusú grammatikáknak nevezzük. • Példa


Formális nyelvek – Grammatikák csoportosítása • Def.: Egy formális nyelvet akkor nevezünk • regulárisnak (3-típusúnak), • környezetfüggetlennek (2-típusúnak), • környezetfüggőnek (1-típusúnak) vagy • általánosnak (0-típusúnak), ha van olyan reguláris, környezetfüggetlen, környezetfüggő vagy általános típusú grammatika, amelyik ezt a nyelvet generálja. Formális nyelvek/36

Formális nyelvek – Grammatikák csoportosítása • Chomsky-féle hierarchia

reguláris g. ⊂ környezetfüggetlen g. ⊂ környezetfüggő g. ⊂ általános g.


Automaták és formális nyelvek

Recommend Documents