8. Tétel Flashcards
Környezetfüggetlen (2-típusú) nyelvek és veremautomaták. (28 cards)
Milyen a 2-típusú (környezetfüggetlen) nyelvtan szabályainak általános alakja?
A szabályok A⟶α alakúak, ahol A nemterminális és α nemüres szimbólumsorozat. Az S⟶λ szabály megengedett, ha S nem szerepel jobb oldalon.
Miért nevezzük “környezetfüggetlennek” a 2-típusú nyelvtanokat?
Az A nemterminális szimbólum a környezetétől függetlenül írható át az α szimbólumláncra.
Mi a deriváció (levezetés) egy környezetfüggetlen nyelvtanban?
Az α0⟹Gα1⟹G⋯⟹Gαn alakú kifejezések sorozata.
Mi a baloldali deriváció?
A deriváció során mindig a bal oldalról nézve a legelső nemterminális szimbólumot helyettesítjük. Jelölése ⟹l.
Mi a jobboldali deriváció?
A deriváció során mindig a jobb oldalról nézve a legelső nemterminális szimbólumot helyettesítjük. Jelölése ⟹r.
Mi a mondatforma egy környezetfüggetlen nyelvtanban?
Az α szimbólumlánc, amire S⟹∗α teljesül, tehát levezethető a kezdőszimbólumból.
Hogyan definiálható egy környezetfüggetlen nyelvtan által generált nyelv?
L(G)={w∈Σ∗∣S⟹∗w}, azaz a kezdőszimbólumból levezethető terminális szavak halmaza.
Mi a derivációs fa egy 2-típusú nyelvtanban?
Véges, rendezett, címkézett fa. Gyökere a kezdőszimbólum, belső csúcsai nemterminálisok, levelei terminálisok.
Miben különböznek a veremautomaták a véges automatáktól?
Állapotot válthatnak input szimbólum olvasása nélkül (üres szimbólum olvasás), és rendelkeznek veremmemóriával.
Mire szolgál a veremmemória a veremautomatában?
Veremábécé szimbólumait tárolja, tartalma módosítható.
Milyen kétféle módon ismerheti fel az input szót egy veremautomata?
Végállapottal való felismerés (input elfogyott, végállapotban van) és üres veremmel való felismerés (input elfogyott, verem kiürült).
Miből áll egy nemdeterminisztikus veremautomata (V=(Q,Σ,Γ,δ,q0,Z0,F))?
Q: állapotok halmaza, Σ: input ábécé, Γ: veremábécé, δ: átmenetfüggvény, q0: kezdőállapot, Z0: verem kezdőszimbóluma, F: végállapotok halmaza.
Mi az átmenetfüggvény (δ) egy veremautomatánál?
δ:Q×(Σ∪{λ})×Γ→P(Q×Γ∗), ami megadja a következő állapotot és a verem módosítását.
Mikor determinisztikus egy veremautomata?
Ha minden q∈Q állapotra és Z∈Γ veremszimbólumra a δ(q,a,Z) halmaz legfeljebb egyelemű, és ha δ(q,λ,Z)=∅, akkor δ(q,a,Z)=∅ minden a∈Σ szimbólumra.
Mi a veremautomata konfigurációja?
Egy (q,w,γ) hármas, ami az aktuális állapotot, a hátralévő inputot és a verem tartalmát írja le.
Mit jelent a ⊢V átmeneti reláció a veremautomatáknál?
Azt jelenti, hogy egy konfigurációból melyik konfigurációba mehet át az automata egy lépésben.
Mi a veremautomata számítása?
Konfigurációk sorozata, C0,C1,…,Ck, ahol C0 kezdő, Ck befejező, és minden lépés szabályos átmenet.
Mikor fogad el egy veremautomata egy input szót?
Ha létezik legalább egy olyan kezdő konfigurációból induló számítás, amely elfogadó konfigurációban ér véget.
Hogyan definiálható a végállapottal felismert nyelv egy veremautomatánál?
L(V)={w∈Σ∗∣(q0,w,Z0)⊢V∗(q,λ,γ),q∈F,γ∈Γ∗}.
Hogyan definiálható az üres veremmel felismert nyelv egy veremautomatánál?
L∅(V)={w∈Σ∗∣(q0,w,Z0)⊢V∗(q,λ,λ),q∈Q}.
Mi a Pumpáló lemma (Nagy Bar-Hillel lemma) célja környezetfüggetlen nyelvekre?
Segítségével bizonyíthatjuk, hogy egy nyelv nem környezetfüggetlen, szükséges feltételt ad meg a környezetfüggetlenségre.
Mi a szintaktikai elemzés alapfeladata?
Eldönteni, hogy egy adott szó (w) eleme-e egy adott 2-típusú nyelvtan (G) által generált nyelvnek (L(G)).
Melyek a két fő típusú elemzési algoritmus a szintaktikai elemzésben?
Felülről lefelé (Top-Down) és alulról felfelé (Bottom-Up) haladó elemzési algoritmusok.
Hogyan működik a felülről lefelé haladó elemzés?
A kezdőszimbólumból (gyökér) kiindulva próbál derivációs fát építeni, aminek határa az input szó.
