A jegyzetről

Ez egy személyes jegyzet, amely csak a könnyű hozzáférés érdekében érhető el publikusan. Mivel a jegyzet saját felhasználásra készül, sok helyen hiányos, hibás. Helyenként üres oldalakat tartalmaz.

Ha mégis ráleltél és hasznosnak találod, én örülök, de ne kizárólag ezt a forrást használd felkészüléshez, ne is idézd sehol!

A tartalom helyességéért, teljességéért tehát felelősséget nem vállalok!

Órarend

A számításelmélet alapjai I. előadás

Alapadatok

Idő: Kedd, 10:00 - 12:00
Helyszín: Déli Tömb 0-822 Mogyoródi József terem
Oktató: Tichler Krisztián, ktichler@inf.elte.hu
Csoport: 1

Értékelés

• Írásbeli vizsga
  • max 60p (20p igaz-hamis, 20p rövid válasz, 20p hosszabb válasz)
  • min ?
• Elővizsga: nem kötelező

Források

• Canvas

Alapfogalmak, nyelvek, grammatikák

• Alapfogalmak, nyelvek, grammatikák
  • Hol használják a formális nyelveket?
  • Alapfogalmak, jelölések
  • Műveletek szavakon
    • Konkatenáció
    • Tükörkép
  • Műveletek nyelveken
  • Egy nyelv iteratív leárt
  • Homomorfizmus
    • h-homomorf képi
  • Formális nyelvek megadása
  • Nyelvcsalások
  • Grammatikák
    • Egylépéses levezetés
    • Többlépéses levezetés
  • Reláció reflexív, tranzitív lezártja
  • Generált nyelv
  • Források

Hol használják a formális nyelveket?

• A természetes nyelvek gépi feldolgozása, matematikai modellezése.
• Programozási nyelvek, fordítóprogramok
• Kódelmélet
• Mintafelismerés
• $\dots$

Alapfogalmak, jelölések

• Ábécé:* egy véges, nemürres halmaz.
• Betűk: az ábécé elemei.
• Szó, (string): Egy $V$ ábécé elemeiből képzett véges sorozat.
• Egy $u=t_1\dots t_n$ szóban lévő betűk számát $(n)$ a szó hosszának nevezzük. ($|u|$ = n)
• $ϵ$: üres szó
• $V^{\ast }$ jelöli a $V$ ábécé feletti szavak halmazát, beleértve az üres szót is.
• $V^{+}=V^{\ast }$ \ $\{ϵ\}$

A $V^{\ast }$ szavait hosszlexikografikus (shortlex) rendezés szerinti sorrendben soroljuk fel.

• Résszó: az $u$ szó a $v$ szó résszava, ha $v=xuy,(u,v,x,y\in V^{\ast })$
• Valódi résszó: ha $u\ne v$ és $u\ne ϵ$
• Prefix: ha $x=ϵ$
• Suffix ha $y=ϵ$

Ezek valódiak, ha $ϵ$-tól és $u$-tól küéönböznek.

• Nyelv: egy $V^{\ast }$ egy $L$ részhalmaza.

• Üres nyelv: $\theta$

• Véges nyelv: $L$ véges, ellenkező esetben végtelen nyelv

• Prefix nyelv: $\mathrm{Pre}(L)=\{u|u\in V^{\ast },uv\in L\mathrm{valamely}v\in V^{\ast }-\mathrm{ra}\}$

• Suffox nyelv: $\mathrm{Suf}(L)=\{u|u\in V^{\ast },vu\in L\mathrm{valamely}v\in V^{\ast }-\mathrm{ra}\}$

Példák:

• $L_1=\{a,ba,ababb,ϵ\}$ (véges)
• $L_2=\{a^i{b}^i|i\ge 0\}$ (végtelen)
• $L_3=\{u{u}^R|u\in V^{\ast }\}$ (végtelen)
• $\dots$

Műveletek szavakon

Konkatenáció

Legyen V egy ábécé továbbá legyenek $u=s_1\dots s_n$ és $t_1\dots t_k$ V feletti szavak. Ekkor az $uv:=s_1\dots s_n{t}_1\dots t_k$ szót az $u$ és a $v$ konkatenáltjának nevezzük.

A konkatenáció mint művelet asszciatív, de általában nem kommutatív.

$V^{\ast }$ a konkatenáció műveletére zárt.

A konkatenáció egységelemes művelet, at egységelem az $ϵ$.

$i$-edik hatvány: egy szó $i$-szeres konkatanációja saját magával. ($u^i$)

Formálisan: $u^0:=ϵ,u^i:=u{u}^{i-1}(i\ge 1)$

Ekkor: $u^{n+k}=u^n{u}^k,(k,n\in \mathbb{N})$

Tükörkép

Legyen $u$ egy $V$ ábécé feletti szó. Az $u$ szó $u^R$-rel jelölt tükörképe (vagy megfordítottja) az a szó, amelyet úgy kapunk, hogy $u$ betűit az eredetihez képest fordított sorrendben konkatenáljuk. Vagyis $u^R$ i-edik betűje éppen $u$-nak az $|u|+1-i$. betűje $(1\le i\le |u|)$.

Ha $u=u^R$, akkor $u$-t palindrom-nak nevezük.

• $(u^R{)}^R=u$
• ${ϵ}^R=ϵ$
• $(uv{)}^R=v^R{u}^R$
• $(u^i{)}^R=(u^R{)}^i,(i\in \mathbb{N})$

Műveletek nyelveken

• Halmazműveletek ($\cup ,\cap ,-,\dots$)
  • Komplementer jelölése: $\overline{L}=V^{\ast }-L$
• Konkatenáció: $L_1{L}_2=\{u_1{u}_2|u_1\in L_1,u_2\in L_2\}$
  • asszociatív
  • nem kommutatív
• $i$-edik hatvány
  • $L^0:=\{ϵ\}$
  • $L^i:=L{L}^{i-1},(i\ge 1)$
  • $L^{k+n}=L^k{L}^n,(k,n\in \mathbb{N})$
• Tükörkép: $L^R:=\{u^R|u\in L\}$

Egy nyelv iteratív leárt

Az $L$ nyelv iteratív lezártja (kleene-lezártja): $$L^{\ast }={\cup }_{i\ge 0}{L}^i$$

AZ $L$ pozitív lezártja: $$L^{+}={\cup }_{i\ge 1}{L}^i$$

$L^{+}=L^{\ast }$, ha $ϵ\in L$ és $L^{+}=L^{\ast }-\{ϵ\}$, ha $ϵ\notin L$.

Homomorfizmus

Legyen $V_1$ és $V_2$ két ábécé. A $h:V_1^{\ast }\to V_2^{\ast }$ leképezést homomorfizmusnak nevezzük, ha teljesülnek a következő feltételek:

• $h$ egyértelmű, azaz minden $u\in V_1^{\ast }$ szóra pontosan egy $v\in v_2^{\ast }$ szó létezik, amelyre $h(u)=v$ teljesül.
• $h(uv)=h(u)h(v)$, minden $u,v\in V_1^{\ast }$-ra.

h-homomorf képi

Legyen $h:V_1^{\ast }\to V_2^{\ast }$ homomorfizmus. A $h$ homomorfizmus $ϵ$-mentes, ha $h(u)\ne ϵ$ bármely $u\in V_1^{+}$ szóra. Legyen $h:V_1^{\ast }\to V_2^{\ast }$ homomorfizmus. Az $L\subseteq V_1^{\ast }$ nyelv h-homomorf képén a $h(L)=\{h(u)|u\in L\}\subseteq V_2^{\ast }$ nyelvet értjük.

Formális nyelvek megadása

• Véges nyelvek esetén felsorolással
• Formulával
• Reguláris kifelyezéssel
• Végtelen nyelvek esetén felsoroló algortimussal
• Generatív grammatikákkal
  • A grammatikák szintetizáló eszközök, egyetlen szimbólumból egy szabályrendszer segítségével szavakat lehet felépíteni. Azon szavak halmaza, melyeket fel lehet építeni egy nyelvet határoz meg, tehát a grammatika szabályrendszere meghatároz egy nyelvet.
• Matematikai gépek, automaták segítségével
  • Az automaták elemző, analitikus eszközök. Az automaták bemenete egy szó, kimenete egy bináris érték. Az automata szabályrendszere szerint feldolgozza a szavakat, csak bizonyos szavak esetén ad igen választ, ezen szavak egy nyelvet alkotnak, melyet az automata szabályrendszere határoz meg.

Figyelem! Nem feltétlen lehet minden eszközzel minden nyelvet megadni. Be fogjuk látni például, hogy reguláris kifejezéssel kevesebb nyelvet lehet leírni mint egy általános grammatikával, de az se elég az összes {0, 1} ábécé feletti nyelv leírásához.

Nyelvcsalások

Ha $X$ egy halmaz, jelölje $\mathcal{P}(X)$ az $X$ halmaz hatványhalmazát, azaz $$\mathcal{P}(X)=\{A|\subseteq X\}$$

Nyelvcsalád alatt nyelveknek egy halmazát értjük.

Grammatikák

Egy $G=⟨N,\Sigma ,P,S⟩$ rendezett négyest grammatikának nevezünk, ha

• $N$ és $\Sigma$ diszjunkt véges ábácék. $N$ elemeit nemterminális, $\Sigma$ elemeit pedig terminális szimbólumnak nevezzük.
• $S\in N$ a grammatika kezdőszimbóluma
• $P$ rendezett $(x,y)$ párok véges halmaza, ahol $x,y\in (N\cup \Sigma {)}^{\ast }$ és $x$ legalább egy nemterminális szimbólumot tartalmaz

A $P$ halmaz elemeit szabályoknak (vagy átírási szabályoknak vagy produkcióknak) hívjuk.

A gyakorlatban az $(x,y)$ jelölés helyett szinte mindig az $x\to y$ jelölést használjuk.

Egylépéses levezetés

Legyen $G=⟨N,\Sigma ,P,S⟩$ egy generatív grammatika és legyen $u,v\in (N,\Sigma {)}^{\ast }$. A $v$ szó közvetlenül vagy egy lépésben levezethető az $u$ szóból $G$-ben, jelölése: $i{⟹}_{G}v$, ha $u=u_{1}x{u}_2$ és
$v=u_{1}y{u}_2$, ahol $u_1,u_2\in (N\cup \Sigma {)}^{\ast }$ és $x\to y\in P$.

Többlépéses levezetés

Legyen $G=⟨N,\Sigma ,P,S⟩$ egy generatív grammatika és legyen $u,v\in (N,\Sigma {)}^{\ast }$. A $v$ szó (több lépésben) levezethető, ha $u=v$ vagy van olyan $n\ge 1$ és $w_0,\dots ,w_n\in (N\cup \Sigma {)}^{\ast }$, hogy $w_{i-1}{⟹}_G{w}_i(1\le i\le n),w_0=u$ és $w_n=v$
Jelölés: $u{⟹}_G^{\ast }v$

Reláció reflexív, tranzitív lezártja

Generált nyelv

Legyen $G=⟨N,\Sigma ,P,S⟩$ egy tetszőleges generatív grammatika. A $G$ grammatika által generált nyelv alatt az $L(G):=\{w|S{⟹}_G^{\ast }w,w\in {\Sigma }^{\ast }\}$ szavakból álló halmazt értjük.

Vegyük észre, hogy a generált nyelv szavai mindig terminális szavak!

Források

• Diasor
• Felvétel

Grammatikák csoportosítása

• 2. Előadás
  • Grammatikák - ismétlés
  • Grammatikák Chomsky féle osztályozása
    • Grammatikák osztályba sorolása
  • Grammatikák a gyakorlatban
  • Chomsky-féle hierarchia
  • Ekvivalens grammatikák és nyelvek
  • Terminánsok elimminációja a szabályok baloldalán
  • Zártsági tulajdonságok
  • Források

Grammatikák - ismétlés

Egy $G=⟨N,\Sigma ,P,S⟩$ rendezett négyest grammatikának nevezünk, ha

• $N$ és $\Sigma$ diszjunkt véges ábácék. $N$ elemeit nemterminális, $\Sigma$ elemeit pedig terminális szimbólumnak nevezzük.
• $S\in N$ a grammatika kezdőszimbóluma
• $P$ rendezett $(x,y)$ párok véges halmaza, ahol $x,y\in (N\cup \Sigma {)}^{\ast }$ és $x$ legalább egy nemterminális szimbólumot tartalmaz

A $P$ halmaz elemeit szabályoknak (vagy átírási szabályoknak vagy produkcióknak) hívjuk.

A gyakorlatban az $(x,y)$ jelölés helyett szinte mindig az $x\to y$ jelölést használjuk.

Legyen $G=⟨N,\Sigma ,P,S⟩$ egy generatív grammatika és legyen $u,v\in (N,\Sigma {)}^{\ast }$. A $v$ szó közvetlenül vagy egy lépésben levezethető az $u$ szóból $G$-ben, jelölése: $i{⟹}_{G}v$, ha $u=u_{1}x{u}_2$ és
$v=u_{1}y{u}_2$, ahol $u_1,u_2\in (N\cup \Sigma {)}^{\ast }$ és $x\to y\in P$.

Legyen $G=⟨N,\Sigma ,P,S⟩$ egy generatív grammatika és legyen $u,v\in (N,\Sigma {)}^{\ast }$. A $v$ szó (több lépésben) levezethető, ha $u=v$ vagy van olyan $n\ge 1$ és $w_0,\dots ,w_n\in (N\cup \Sigma {)}^{\ast }$, hogy $w_{i-1}{⟹}_G{w}_i(1\le i\le n),w_0=u$ és $w_n=v$
Jelölés: $u{⟹}_G^{\ast }v$

Grammatikák Chomsky féle osztályozása

Legyen $G=⟨N,\Sigma ,P,S⟩$ egy grammatika. A $G$ grammatika $i$-típusú ($i=0,1,2,3$), ha $P$ szabályhalmazára teljesülnek a következők:

• $i=0$ eset: nincs korlátozás
• $i=1$ eset:
  • $P$ minden szabálya $u_{1}A{u}_2\to u_{1}v{u}_2$ alakú, ahol $u_1,u_2,v\in (N\cup \Sigma {)}^{\ast },A\in N$ és $v\ne ϵ$
  • Egyetlen kivételt megengedünk: $P$ tartalmazhatja az $S\to ϵ$ szabályt, de csak abban az esetben, ha $S$ nem fordul elő $P$ egyetlen szabályának jobb oldalán sem. Korlátozott $ϵ$ szabály (KES)
• $i=2$ eset: $P$ minden szabálya $A\to v$ alakú, ahol $A\in N$ és $v\in (N\cup \Sigma {)}^{\ast }$
• $i=3$ eset: $P$ minden szabálya vagy $A\to uB$ vagy $A\to u$ alakú, ahol $A,B\in N$ és $u\in {\Sigma }^{\ast }$

Jelölje ${\mathcal{G}}_i$ az $i$-típusú gramatikák osztályát.

Grammatikák osztályba sorolása

Legyen $G$ egy grammatika. A következő esetek lehetségesek:

$G\in {\mathcal{G}}_3,{\mathcal{G}}_2,{\mathcal{G}}_1,{\mathcal{G}}_0$
Lokálisan minden szabály $3$-as és teljesül a KES.

$G\in {\mathcal{G}}_3,{\mathcal{G}}_2,{\mathcal{G}}_0$
Lokálisan minden szabály $3$-as den nem teljesül a KES.

$G\in {\mathcal{G}}_2,{\mathcal{G}}_1,{\mathcal{G}}_0$
Lokálisan minden szabály $2$-as, van $3$-as szabály és teljesül a KES.

$G\in {\mathcal{G}}_2,{\mathcal{G}}_0$
Lokálisan minden szabály $2$-es, van nem $3$-as szabály de nem teljesül a KES.

$G\in {\mathcal{G}}_1,{\mathcal{G}}_0$
Lokálisan minden szabály $1$-es, van nem $2$-es szanály és teljesül a KES.

$G\in {\mathcal{G}}_0$
Van nem $1$-es szabálya vagy minden szabály $1$-es, van nem $2$-es szabálya és nem teljesül a KES.

${\mathcal{L}}_i:=\{L|\exists G\in {\mathcal{G}}_i\mathrm{hogy}L=L(G)\}$ jelöli az $i$-típusú nyelvek nyelvosztályát, elemeit $i$-típusú nyelveknek nevezzük.

• A 0-típusú grammatikákat mondatszerkezetű (phrase-structure) grammatikáknak is nevezzük, ami nyelvészeti eredetükre utal.
• A 1-típusú grammatikák a környezetfüggő (context-sensitive) grammatikák, mert szabályai olyanok, hogy, egy A nemterminális valamely előfordulása egy $v$ szóval csak $u1$ és $u2$ kontextus jelenlétében helyettesíthető.
• 2-típusú grammatikákat környezetfüggetlen (context-free) grammatikáknak mondjuk, mert szabályai olyanok, hogy az $A$ nemterminális $v$-vel való helyettesítése bármely kontextusban megengedett.
• A 3-típusú grammatikákat reguláris (regular) vagy véges állapotú (finite state) grammatikáknak hívjuk, a véges állapotú automatákkal való kapcsolatuk miatt.
• 0,1,2,3-típusú nyelvek osztályait rendre rekurzíven felsorolható, környezetfüggő, környezetfüggetlen, valamint reguláris nyelvosztálynak is mondjuk.

Grammatikák a gyakorlatban

• BNF (Backus-Naur Form).

A BNF egy széles körben használt metanyelv melynek segítségével szabályok alkothatók meg (például egy programozási nyelv szintaktikai szabályai).

Építőkövei:

• $⟨\mathrm{n}\acute{\mathrm{e}}\mathrm{v}⟩$, fogalmak (nemdeterminánsok)
• $::=$ a szabályok bal- és jobboldalának elválasztása
• a sztringek alkotóelemei (terminálisok)

Egy szabály bal- és jobboldalból áll, köztük ::=, baloldalon pontosan 1 fogalom, jobboldalon terminálisok és fogalmak véges sorozata állhat.

A BNF megfelel a környezetfüggetlen grammatikának.

Chomsky-féle hierarchia

A grammatikák alakja alapján ${\mathcal{G}}_3\subseteq {\mathcal{G}}_2\subseteq {\mathcal{G}}_0$ és ${\mathcal{G}}_1\subseteq {\mathcal{G}}_0$

Később azt is meg fogjuk mutatni, hogy a következö tétel fennáll: $${\mathcal{L}}_3\subset {\mathcal{L}}_2\subset {\mathcal{L}}_1\subset {\mathcal{L}}_0$$

Ekvivalens grammatikák és nyelvek

Amíg minden grammatika egyetlen nyelvet generál, ez fordítva nem igaz. Ugyanazt a nyelvet több különböz ̋o grammatika is generálhatja.

A $G_1$ és $G_2$ grammatikák ekvivalensek egymással, ha ugyanazt a nyelvet generálják, azaz $L(G_1)=L(G_2)$ teljesül.

Az $L_1$ és $L_2$ nyelveket egymással gyengén ekvivalensnek nevezzük, ha legfeljebb az $ϵ$ tartalmazásában térnek el egymástól, azaz ha $(L_1-L_2)\cup (L_2-L_1)\subseteq \{ϵ\}$.

A $G_1$ és $G_2$ grammatikákat gyengén ekvivalensnek nevezzük, ha egymással gyengén ekvivalens nyelveket generálnak.

Terminánsok elimminációja a szabályok baloldalán

Minden $G=⟨N,\Sigma ,P,S⟩$ grammatikához van vele ekvivalens és azonos típusú $G^{\prime }=⟨N^{\prime },\Sigma ,P^{\prime },S⟩$ grammatika, melyre $x\in (N^{\prime }{)}^{+}$ minden $x\to y\in P^{\prime }$-re

Zártsági tulajdonságok

Az unió, konkatenáció és iteratív lezárás műveleteket reguláris műveleteknek nevezzük.

Egy $\mathcal{L}$ nyelvcsalád zárt a $\phi :(L_1,\dots ,L_n)\to \phi (L_1,\dots ,L_n)$ $n$-változós nyelvműveletekre nézve, ha minden $L_1,\dots L_n\in \mathcal{L}$ esetén $\phi (L_1,\dots L_n)\in \mathcal{L}$

${\mathcal{L}}_i$ zárt a reguláris műveletekre nézve ($i=0,1,2,3$)

Források

• Diasor
• Felvétel

Lineáris grammatikák, 3-típusú grammatikák normálformája, reguláriws kifelyezések

• Lineáris grammatikák, 3-típusú grammatikák normálformája, reguláriws kifelyezések
  • Lineáris grammatikák és nyelvek
    • Bal és jobblineáris nyelvek
    • L3 tükrözésre való zártsága
  • 3-típusú grammatikák normálformája
  • Reguláris kifelyezések
    • Leíró erő
    • Arden tétele
  • Források

Lineáris grammatikák és nyelvek

Egy $G=⟨N,\Sigma ,P,S⟩$ környezetfüggetlen grammatikát lineárisnak nevezünk, ha minden szabálya vagy

1. $A\to u,A\in N,u\in {\Sigma }^{\ast }$ vagy
2. $A\to u_{1}B{u}_2$ alakú, ahol $A,B\in N$ és $u_1,u_2\in {\Sigma }^{\ast }$

A $G$ lineáris grammatikát bal-lineárisnak nevezzük, ha minden 2. alakú szabályban $u_1=ϵ$.

A $G$ lineáris grammatikát jobb-lineárisnak nevezünk, ha minden 2. alakú szabályban $u_2=ϵ$.

Bal és jobblineáris nyelvek

Egy $L$ nyelvet lineárisnak, bal-lineárisnak, illyetve jobb-lineárisnak mondunk, ha van olyan $G$ lineáris, bal-lineáris, illetve jobb-lineáris grammatika, amelyre $L=L(G)$ teljesül.

Minden bal-lineáris grammatika reguláris (3-típusú) nyelvet generál.

L3 tükrözésre való zártsága

Minden $G=⟨N,\Sigma ,P,S⟩$ jobb-lineáris grammatikához meg tudunk konstruálni egy $G^{\prime }$ bal-lineáris grammatikát, amely $L(G)$ tükörképét generálja.

Következmény:

1. ${\mathcal{L}}_3$ zárt a tükrözés műveletére nézve.
2. Minden reguláris nyelv generálható bal-lineáris grammatikával.

3-típusú grammatikák normálformája

Egy $G=⟨N,\Sigma ,P,S⟩$ grammatika 3-as normálformájú, ha minden $P$-beli szabály alakja

• $X\to aY,X,Y\in N,a\in \Sigma$ vagy
• $X\to ϵ$, ahol $X\in N$

Minden reguláris (azaz 3-típusú) nyelv generálható 3-as normálformájú grammatikával.

Reguláris kifelyezések

Vegyük észre, hogy minden véges nyelv reguláris. Tudjuk továbbá, hogy az ${\mathcal{L}}_3$ nyelvosztály zárt az unió, a konkatenáció és az iteratív lezárt műveletekre nézve.

Következésképpen, kiindulva véges számú véges nyelvből és az előzőekben felsorolt reguláris műveleteket véges sokszor alkalmazva reguláris nyelvet kapunk.

Kérdés az, hogy vajon az eljárással minden reguláris nyelvet ekő tudunk-e állítani, azaz ez a módszer elégséges-e az ${\mathcal{L}}_3$ nyelvosztály leírására?

Legyenek $V$ és $V^{\prime }=\{\theta ,ϵ,.,+,\ast ,(,)\}$ diszjunkt ábécék. A $V$ ábécé feletti reguláris kifelyezéseket rekurzív módon következőképpen definiáljuk:

• $\theta$ reguláris kifejezés $V$ felett
• $ϵ$ reguláris kifejezés $V$ felett
• $a$ reguláris kifejezés $V$ felett, ha $a\in V$
• Ha $R$ reguláris kifejezés $V$ felett, akkor $R^{\ast }$ is reguláris kifejezés $V$ felett
• Ha $Q$ és $R$ reguláris kifejezések $V$ felett, akkor $(Q\cdot R)$ is
• Ha $Q$ és $R$ reguláris kifejezések $V$ felett, akkor $(Q+R)$ is

Minden egyes $R$ reguláris kifejezés egy-egy $L(R)$-rel jelölt reguláris nyelvet határoz meg, amelyeket az alábbi rekurzióval definiálunk:

1. $L(\theta ):=\theta$
2. $L(ϵ):=\{ϵ\}$
3. $L(a):=\{a\}$
4. $L(R^{\ast }):=L(R{)}^{\ast }$, ha $R$ reguláris kifejezés
5. $L(Q\cdot R):=L(Q)L(R)$, ha $Q,R$ reguláris kifejezések
6. $L(Q+R):=L(Q)\cup L(R)$, ha $Q,R$ reguláris kifejezések

A műveletek precedens sorrendje: $\ast ,.,+$, ennek és az asszociatív szabályok figyelembevételével bizonyos zárójelpárok elhagyhatók.

Leíró erő

Minden reguláris kifejezés reguláris nyelvet ír le, és megfordítva, minden reguláris nyelvhez megadható egy, ezen nyelvet leíró reguláris kifejezés.

Arden tétele

Ezt a tételt később a reguláris kifejezések véges automatákkal való kapcsolatának vizsgálatakor fogjuk használni.

Adottak az $R$ és $Q$ reguláris kifejezések. A $P=R+P\cdot Q$ egyenletnek $P$-re vonatkozó megoldása $P=R\cdot Q^{\ast }$. Amennyiben $ϵ\notin L(Q)$, akkor az egyenletnek ez az egyetlen megoldása.

Források

• Diasor
• Felvétel

Véges automaták

• Véges automaták
  • Determinisztikus véges automata
    • Az átmenetfüggvény kiterjesztése
  • Nemdeterminisztikus véges automata
    • Szabály alapú alternatív megközelítés
  • Redukció
    • Egylépéses redukció
    • Többlépéses Redukció
    • Elfogadott elv
  • Véges automaták és reguláris nyelvek
  • Véges automata determinizálása
  • Források

Formális nyelvek megadása nemcsak generatív eszközökkel, hanem felismerő eszközökkel is lehetséges. Ilyen eszközök az automaták, amelyek szavak feldolgozására és azonosítására alkalmasak.

Nyelvek megadására a grammatikák a szintetizáló, az automaták analitikus megközelítést alkalmaznak.

Az automaták egy szó feldolgozása után kétféle választ adhat, vagy elfogadja, vagy elutasítja a bemenetet.

• Diszkrét időintervallumokban végrehajtott lépések sorozatán keresztül működik
• A kezdőállípotból indul, az inputszó az inputszalagon helyezkedik el, az olvasófej őedig az inputszó legbaloldalibb szimbólumánál áll.
• Az automata, miután elolvasott egy szimbólumot, az olvasófejet egy pozícióval jobbra mozgatja, majd állapotot vált az állapot-átmenet függvénye szerint.
• Amennyiben az automata még nem olvasta végig a teljes inputot és elfogadó állapotba ér nem dönt még az elfogadásról/elutasításról, tovább m ̋uködik a szabályai szerint.
• Ha az automata elolvasta az inputot, akkor megáll és aktuális állapota alapján válaszol, hogy felismeri vagy elutasítja a bemeneti szót.

Determinisztikus véges automata

Egy rendezett ötös, $$A=⟨Q\Sigma ,\delta ,q_0,F⟩$$ ahol

• $Q$ az állapotok véges, nemüres halmaza
• $\Sigma$ az inputszimbólumok ábécéje
• $\delta :Q\times \Sigma \to Q$ leképzés az ún. állapot-átmenet függvény
• $q_0\in Q$ a kezdőállapot
• $F\supseteq Q$ az elfogadó állapotok halmaza

Az átmenetfüggvény kiterjesztése

Legyen $A$ egy determinisztikus véges automata.

A $\delta$ leképzés kiterjesztése az a $\hat{\delta }:Q\times {\Sigma }^{\ast }\to Q$ teljes leképzés, amelyre

• $\hat{\delta }(q,ϵ):=q$
• $\hat{\delta }(q,xa):=\delta (\hat{\delta }(q,x),a)(\forall x\in {\Sigma }^{\ast },a\in \Sigma )$

$\delta (q,u)$ tehát az az állapota az automatának, ahova a $q$ állapotból indulva az $u$ szó feldolgozása után eljut.

Ha $\hat{\delta }(q_0,u)\in F$, akkor az $u$ inputot elfogadja $A$, ha $\hat{\delta }(q_0,u)\notin F$, akkor elutasítja.

elhagyjuk.

Nemdeterminisztikus véges automata

Determinisztikus véges automata:

• A $\delta$ függvény mindenütt értelmezett és egyértékű. Azaz minden $(q,a)\in Q\times \Sigma$ párra pontosan egy olyan s állapot létezik, amelyre $\delta (q,a)=s$ fennáll.

Nemdeterminisztikus véges automata:

• Megengedjük az állapot-átmenet függvény többértékűségét, azaz $\delta$ ekkor egy $Q\times \Sigma \to P(Q)$ leképezés.
• Több kezdoállapot is megengedett (azaz a kezdőállapotok $Q_0$ halmazára $Q_0\subseteq Q$).
• Úgy interpretálhatjuk, hogy a $q\in Q$ állapotból az $a\in \Sigma$ betű olvasására a gép egy tetszoleges $\delta (q,a)$-beli új állapotba léphet, azaz adott inputra több működés lehetséges.
• Mivel $\varnothing \in P(Q)$, ezért elofordulhat, hogy az $\delta (q,a)=\varnothing$ valamely $(q,a)$-ra, ilyenkor elakad a gép.
• Akkor fogad el egy bemenetet, ha van legalább egy $F$-beli állapotban termináló működése.

A nemdeterminisztikus véges automata egy rendezett ötös, $$A=⟨Q,\Sigma ,\delta ,Q_0,F⟩$$ ahol

• $Q$ az állapotok egy véges, nemüres halmaza
• $\Sigma$ az inputszimbólumok ábécéje
• $\delta :Q\times \Sigma \to \mathcal{P}(Q)$ leképzés, az állapot-átmenet függvény
• $Q_0⫅Q$ a kezdőállapotok halmaza
• $F⫅Q$ az elfogadó állapotok halmaza.

A determinisztikus véges automata a nemdeterminisztikus véges automata egy speciális esetének tekinthető.

Szabály alapú alternatív megközelítés

Legyen $A=⟨Q,\Sigma ,\delta ,Q_0,F⟩$ egy nemdeterminisztikus véges automata-

Az átmenetek szabály alapon történő megadása:

Az $A$-hoz tartozó $M_{\delta }$ szabályrendszerhez minden $p,q\in Q,a\in \Sigma ,p\in \delta (q,a)$ esetén adjunk hozzá a $$qa\to p$$ alakú átírási szabályt, azaz $$M_{\delta }=\{qa\to p|p,q\in Q,a\in \Sigma ,p\in \delta (q,a)\}$$

Redukció

Egylépéses redukció

Láttuk, hogy az automata további műuködése mindig csak az aktuális, $q\in Q$ állapottól és a bemenet még hátralévo olvasatlan $w\in {\Sigma }^{\ast }$ suffixétol függ. Ez motiválja a következőt.

Egy $u\in Q{\Sigma }^{\ast }$ szót az $A=⟨Q,\Sigma ,\delta ,Q_0,F⟩$ NDVA egy konfigurációjának nevezzük.

Legyen $A=⟨Q,\Sigma ,\delta ,Q_0,F⟩$ egy véges automata és legyenek $u,v\in Q{\Sigma }^{\ast }$ konfigurációk. Az $A$ automata az $u$ szót egy lépésben a $v$ szóra redukálja, ha van olyan $qa\to p\in M_{\delta }$ szabály, és olyan $w\in {\Sigma }^{\ast }$ szó, hogy $u=qaw$ és $v=pw$ teljesül.

Többlépéses Redukció

Az $A=⟨Q,\Sigma ,\delta ,Q_0,F⟩$ véges automata az $u\in Q{\Sigma }^{\ast }$ szót a $v\in Q{\Sigma }^{\ast }$ szóra redukálja, ha vagy $u=v$ vagy valamelyik $k\ge 1$-rw léteznek $w_0,\dots ,w_k$ konfigurációk, melyekre $w_{i-1}⟹w_i(1\le i\le k),w_0=u$ és $w_k=v$

Elfogadott elv

Az $A=⟨Q,\Sigma ,\delta ,Q_0,F⟩$ nemdeterminisztikus véges automata által elfogadott nyelv alatt az $L(A)=\{u\in {\Sigma }^{\ast }|q_{0}u⟹p\mathrm{valamely}{q}_0\in Q_0-\mathrm{ra}\acute{\mathrm{e}}\mathrm{s}p\in F-\mathrm{re}\}$ nyelvet értjük.

Véges automaták és reguláris nyelvek

Minden $A$ nemdeterminisztikus véges automatához meg tudunk adni egy 3-tíípusú $G$ grammatikát, úgí hogy $L(G)=L(A)$ teljesül.

Minden 3-típusú $G$ grammatikához meg tudunk adni egy $A$ nemdeterminisztikus véges automatát úgy, hogy $L(A)=L(G)$ teljesül.

Véges automata determinizálása

Minden $A=⟨Q,\Sigma ,\delta ,Q_0,F⟩$ nemdeterminisztikus véges automatákhoz megkonstruálható egy $A^{\prime }=⟨Q^{\prime },\Sigma ,{\delta }^{\prime },q_0^{\prime },F^{\prime }⟩$ determinisztikus véges automata úgy, hogy $L(A^{\prime })=L(A)$ teljesül.

$$\begin{gathered} Q^{\prime }:=\mathcal{P}(Q),q_0^{\prime }:=Q_0,F^{\prime }:=\{q^{\prime }\in Q^{\prime }|q^{\prime }\cap F\ne 0\}, \\ {\delta }^{\prime }(q^{\prime },a):={\cup }_{q\in q^{\prime }}\delta (q,a) \end{gathered}$$

Tehát mind a determinisztikus véges automaták, mind a nemdeterminisztikus véges automaták reguláris (${\mathcal{L}}_3$-beli) nyelveket leíró formális eszközök.

Források

• Diasor
• Felvétel

Véges automata determinizálása, összefüggő automaták, algoritmikus eldöntési probléma

• 5. Véges automata determinizálása, összefüggő automaták, algoritmikus eldöntési probléma
  • Véges automata determinizálása
  • L3 további zártsági tulajdonságia
  • Összefüggő automata
  • Algoritmikus problémák
    • 3as típusú grammatikák algoritmikus problémái
      • Eldönthető, hogy egy reguláris grammatika az üres nyelvet generálja-e.
      • Eldönthető, hogy két reguláris grammatika által generált nyelv diszjunkt-e.
      • Eldönthető, hogy két reguláris grammatika ugyanazt a nyelvet generálja-e vagy sem.
      • Eldönthető, hogy egy reguláris grammatika bővebb, vagy egyenlő nyelvet generál-e, mint egy másik.
      • A 3-as típusú grammatikák szóproblémája hatékonyan eldönthető.
  • Források

Véges automata determinizálása

Minden $A=⟨Q,\Sigma ,\delta ,Q_0,F⟩$ véges nemdeterminisztikus automatához megkonstruálható egy $A^{\prime }=⟨Q^{\prime },\Sigma ,{\delta }^{\prime },q_0^{\prime },F^{\prime }⟩$ véges determinisztikus automata úgy, hogy $L(A)=L(A^{\prime })$ teljesül.

L3 további zártsági tulajdonságia

${\mathcal{L}}_3$ zárt a komplementerre, a metszetre és a különbségre.

Tehát az alábbi formális eszközök mind az ${\mathcal{L}}_3$ nyelvosztályt írják le egy adot ábécé felett:

• jobblineáris grammatikák
• ballineáris grammatikák
• 3-as normálformájú grammatikák
• reguláris kifelyezések
• a komplementer, metszet, különbség, tükörkép, pozitív lezárt műveletekkel bővített úgynevezett általánosított kifejezések
• véges determinisztikus automaták
• véges nemdeterminisztikus automaták

Összefüggő automata

Legyen $A=⟨Q,\Sigma ,\delta ,q_0,F⟩$ véges determinisztikus automata. A $q$ állapotot a kezdőállapotból elérhetőnek mondjuk, ha létezik $q_{0}x⟹q$ redukció, ahol $x\in {\Sigma }^{\ast }$

Az $A=⟨Q,\Sigma ,\delta ,q_0,F⟩$ véges determinisztikus automatát összefüggőnek mondjuk, ha minden állapota elérhető a kezdőállapotból.

$q$ elérhető a kezdőállapotból, akkor és csak akkor, ha van olyan $x\in {\Sigma }^{\ast }$, hogy $\delta (q_0,x)=q$

Algoritmikus problémák

Akkor beszélünk algoritmukis eldöntési problémáról, ha a bemenet egy olyan objektum, mely egy adott végtelen halmazból kerülhet ki, kimenete pedig igen/nem.

Olyan algoritmust keresünk, amely kellően általános ahhoz, hogy a végtelen lehetséges bemenet bármelyike esetén alkalmazható legyen.

Egy probléma eldönthető, ha létezik olyan minden lehetséges bemenet esetén termináló algoritmus, amelyik a helyes választ adja.

3as típusú grammatikák algoritmikus problémái

Eldönthető, hogy egy reguláris grammatika az üres nyelvet generálja-e.

Bizonyítás: A tanultak szerint a grammatikához megadható olyan A véges determinisztikus automata, amelyik a grammatika által generált nyelvet ismeri fel. Az automata pontosan akkor nem ismer fel egyetlen szót sem, ha kezdőállapotából minden végállapota elérhetetlen. Ez viszont algoritmikusan eldönthető.

Eldönthető, hogy két reguláris grammatika által generált nyelv diszjunkt-e.

Bizonyítás: Generálják a $G_1$ és $G_2$ reguláris grammatikák rendre az $L_1$ és $L_2$ nyelveket. Az $L_3=(L_1\cap L_2)\cup (L_1\cap L_2)$ nyelv szintén reguláris, így van olyan $G_3$ reguláris grammatika, amely $L_3$-at generálja. Ekkor azonban $L_1=L_2$ akkor és csak akkor, ha $L_3=\varnothing$, amely a fentiek szerint eldönthető.

Eldönthető, hogy két reguláris grammatika ugyanazt a nyelvet generálja-e vagy sem.

Bizonyítás: Generálják a $G_1$ és $G_2$ reguláris grammatikák rendre az $L_1$ és $L_2$ nyelveket. Az $L_3=(L_1\cap {\bar{L}}_2)\cup ({\bar{L}}_1\cap L_2)$ nyelv szintén reguláris, így van olyan $G_3$ reguláris grammatika, amely $L_3$-at generálja. Ekkor azonban $L_1=L_2$ akkor és csak akkor, ha $L3=\varnothing$, amely a fentiek szerint eldönthető.

Eldönthető, hogy egy reguláris grammatika bővebb, vagy egyenlő nyelvet generál-e, mint egy másik.

Bizonyítás: Generálják a $G_1$ és $G_2$ reguláris grammatikák rendre az $L_1$ és $L_2$ nyelveket. Az $L_3=(L_1\cap {\bar{L}}_2)=L_1\setminus L_2$ szintén reguláris. Ennek üressége eldönthető, ami ekvivalens azzal, hogy $L_1\subseteq L_2$

A 3-as típusú grammatikák szóproblémája hatékonyan eldönthető.

Szóprobléma: Adott $G$ grammatika és $u\in {\Sigma }^{\ast }$. $u\stackrel{?}{\in }L(G)$

Bizonyítás: Legyen $G=⟨N,\Sigma ,P,S⟩$ egy 3-as típusú grammatika normálformában adva és $u=t_1\dots t_n$ a levezetendő szó.

Az algoritmus rekurzívan kiszámol egy $N$ részhalmazból álló $H_i(0\le i\le n)$ sorozatot. $H_i$-ból $H_{i+1}$ (csak $G$-től függő) konstans időben számolható.

$H_0:=\{S\},H_{i+1}:=\{A\in N|\exists B\in H_i\wedge B\to t_{i+1}A\in P\}$

Könnyen látható, hogy $H_i$ azon nemterminálosok halmaza, melyek pontosan $i$ leezetési lépés után a mondatforma végén állhatnak.

Tehát ha $F=\{A\in N|A\to ϵ\in P\}$, akkot nyilván $$u\in L(G)⟺H_n\cap F\ne \varnothing$$

Források

• Diasor
• Felvétel

Maradéknyelv, myhill-nerode tétel, minimális-, redukált-, faktor automata,

• Maradéknyelv, myhill-nerode tétel, minimális-, redukált-, faktor automata,
  • Maradéknyelv
    • Nyelv adott szóra vonatkozó maradéknyelve
    • Automata adott állapotra vonatkozó maradéknyelve
  • Myhill Nerode tétel
    • Példa
  • Minimális automata
    • Minimális automata készítése
  • Redukált automata
  • Faktorautomata
  • Összegzés
  • Források

Maradéknyelv

Nyelv adott szóra vonatkozó maradéknyelve

Az $A$ és $A^{\prime }$ automaták ekvivalensek, ha $L(A)=L(A^{\prime })$.

Adott $L\subset {\Sigma }^{\ast }$ nyelv $p\in {\Sigma }^{\ast }$-ra szóra vonatkozó maradéknyelve $L_p$, ahol $L_p:=\{v\in {\Sigma }^{\ast }|pv\in L\}$

$L_p$ tehát azokat a szavakat tartalmazza, amelyekkel $p$-t jobbról kiegészítve $L$-beli szót kapunk.

Automata adott állapotra vonatkozó maradéknyelve

Legyen $A=⟨Q,\Sigma ,\delta ,q_0,F⟩$ véges determinisztikus automata.

Az L(A, q) \coloneqq {v \in \Sigma^* \vert\ qv \implies p, p \in F} nyelvet az $A$ automata $q\in Q$ állapotra vonatkozó maradék nyelvének nevezzük.

Alternatív definíció: $L(A,q):=\{v\in {\Sigma }^{\ast }|\delta (q,v)\in F\}$

Az $L(A,q)$ tehát azokat a szavakat tartalmazza, amelyek hatására az automata $q$-ból indítva végállapotba kerül.

Azaz, $L(A,q)$ lenne az elfogadott nyelv, ha a kezd˝oállapotot q-ra változtatnánk.

Tulajdonságai:

• $L(A,q{)}_w=L(A,\delta (q,w))(w\in {\Sigma }^{\ast })$
• $L(A,q_0)=L(A)$
• $ϵ\in L(A,q)⟺q\in F$

Myhill Nerode tétel

$$L\in {\mathcal{L}}_3⟺|\{L_p{\}}_{p\in {\Sigma }^{\ast }}|<\infty$$ ahol $\Sigma$ az $L$ nyelv ábécéje.

Példa

$L=\{a^n{b}^n|n\in \mathbb{N}\}$.

Ekkor $L_{a^k}=\{a^{n-k}{b}^n|n\ge k\}(k\in \mathbb{N})$

$b^i\in L_{a^k}⟺i=k$.

Tehát ez a végtelen sok maradéknyelv páronként különböző, így $L\notin {\mathcal{L}}_3$

ZH-n jól használható determinisztikus automata kreálására!

Minimális automata

Mivel $A_L^{MN}$ állapothalmaza $\{L_u{\}}_{u\in {\Sigma }^{\ast }}$, ezért az alábbi következményt kapjuk:

Az $A_L^{MN}$ automata állapotszáma kisebb vagy egyenlő, mint a tetszőleges, az $L$ nyelvhez adott véges, determinisztikus automata állapotszáma.

Az $A$ véges determinisztikus automata minimális állapotszámú, ha nincs olyan $A$-val ekvivalens $A^{\prime }$ véges determinisztikus automata, aminek kevesebb állapota van mint $A$-nak. Egy $L$ nyelv minimális automatája alatt egy $L$-et felismerő minimális véges determinisztikus automatát értünk.

Minimális automata készítése

Cél: Adott automatához minél kevesebb állapotú, vele ekvivalens, azaz az eredeti automata által felismert nyelvet elfogadó automatát megadni. Két lépésben fogjuk ezt elérni:

1. Összefüggővé alakítás:

Nyilván átmeneteikkel együtt elhagyhatók azok az állapotok, melyekbe nem tud eljutni az automata. Az átmenetdiagramon ez annak felel meg, hogy nincs a kezd˝oállapotból irányított út a csúcsba.

2. Ekvivalens állapotok összevonása:

Ha két állapotból pontosan ugyanazon szavak hatására kerül az automata végállapotba, akkor az elfogadás szempontjából mindegy, hogy a m˝uködés során a két állapotba kezül melyikbe került az automata. Ezek az állapotok nyilván összevonhatók.

Redukált automata

Legyenek $q,q^{\prime }\in Q$ állapotok. $q$-t és $q^{\prime }$-t nevezzük megkülönbözhetetlennek, ha $L(A,q)=L(A,q^{\prime })$

Egy véges determinisztikus automata redukált, ha nincsenek megkülönböztethetetlen állapotai.

Faktorautomata

Legyenek $A=⟨Q,\Sigma ,q_0,F⟩$ és $A^{\prime }=⟨Q^{\prime },\Sigma ,{\delta }^{\prime },q_0^{\prime },F^{\prime }⟩$ véges, determinisztikus automaták. A két automata izomorf, ha van olyan $\phi :Q\to Q^{\prime }$ bijekció, melyre

• $\phi (q_0)=q_0^{\prime }$
• $\phi (F):={\cup }_{q\in F}\{\phi (q)\}=F^{\prime }$
• $\forall q\in Q,t\in \Sigma$ esetén $\phi (\delta (q,t))={\delta }^{\phi (q),t}$

Tétel:

Az $A$ determinisztikus véges automata $A/$~ faktorautomatája

1. ekvivalens $A$-val
2. redukált
3. ha $A$ összefüggő, akkor izomorfia erejéig az egyetlen összefüggő, redukált $A$-val ekvivalens automata.

Összegzés

Tehát egy A véges determinisztikus automatához minimális automatát készíthetünk úgy, hogy

1. az elérhetetlen állapotait elhagyjuk ezzel előállítva egy $A$-val ekvivalens összefüggő automatát,
2. majd a már összefüggő automata $i\sim$ relációnak meghatározása segítségével a fenti módon algoritmikusan előállítunk egy redukált automatát.

• Az így kapott automata, összefüggő, redukált és ekvivalens $A$-val, ezért korábbi tételünk alapján izomorf az $A/\sim$-vel,
• mivel az $A_L^{MN}$ automata, ahol $L=L(A)$ szintén összefüggő, redukált (minden minimális automata redukált kell legyen) és $A$-val ekvivalens, ezért $A_L^{MN}$ ugyanezen tétel alapján szintén izomorf a faktorautomatával,
• mivel $A_L^{MN}$ minimális automata, ezért a faktorautomata és az $i\sim$ által algoritmikusan meghatározott automata is minimális automata, tételünk szerint ezek izomorfak egymással.

Források

• Diasor

Nyelvi egyenletrendszerek megoldása, általánosított automata

• Nyelvi egyenletrendszerek megoldása, általánosított automata
  • Lineáris nyelvi egyenletrendszerek megoldása
  • Automata adott állapotra vonatkozó maradéknyelve
  • Általánosított automata
  • Kis Bar-Hillel lemma
  • Források

Lineáris nyelvi egyenletrendszerek megoldása

Arden tétele általánosabban:

Legyenek az $L_1$ és $L_2$ nyelvek adottak. Az X = L_1 X \cup \L_2 egyenletnek $X$-re vonatkozó megoldása $X=L_1^{\ast }L2$. Amennyiben $ϵ\notin L_1$, akkor az egyenletnek ez az egyetlen megoldása.

Legyen $x=Mx\cup v$ nyelvi egyenletrendszer, ahol az $M$ nyelvmátrix és a $v$ nyelvvektor adott az $x$ ismeretlen nyelvekből álló vektort keressük. Ha $$\mathcal{L}={\cup }_{j=1}^n{\cup }_{k=1}^n\{L_{j,k}\}\cup {\cup }_{j=1}^n\{L_j\}\subseteq {\mathcal{L}}_i(i\in \{0,1,2,3\})$$ és $ϵ\notin L_{jk}(1\le j\le n,1\le k\le n)$, akkor az egyenletrendszernek egyértelműen létezik $\mathcal{L}$-beli megoldása, és ez a megoldás $\mathcal{L}$ elemeiből a reguláris nyelvműveletekkel épül fel.

Automata adott állapotra vonatkozó maradéknyelve

Egy $A=⟨Q,\Sigma ,\delta ,q_0,F⟩$ determinisztikus véges automata egy $q\in Q$ állapotra vinatkozó maradéknyelve alatt az $L(A,q):=\{v\in {\Sigma }^{\ast }|\delta (q,v)\in F\}$ nyelvet értjük.

Az $L(A,q)$ tehát azokat a $v$ szavakat tartalmazza, amelyek hatására az automata $q$-ból végállapotba kerül.

Tehát $L(A,q_0)=L(A)$ és $ϵ\in L(A,q)⟺q\in F$

Vegyük továbbá észre, hogy fennállnak a következő nyelvi egyenletek:

$$L(a,q)={\cup }_{t\in \Sigma }tL(A,\delta (q,t))\cup \{\varnothing (q\notin F),\{ϵ\}(q\in F)\}$$

ahol $tL:=\{tu|u\in L\}(t\in \Sigma )$

A maradéknyelvekre vonatkozó egyenletrendszert megoldjuk ($L(A,q_0)$ az érdekes). A megoldás egyértelműsége az előző tételből, de az $L(A,q)$-k egyértelműségéből is adódik.

Általánosított automata

Legyen $\mathcal{R}(\Sigma )$ a $\Sigma$ feletti reguláris kifejezések halmaza.

Az általános automata definíciója megegyezik a véges nemdeterminisztikus automata definíciójával azzal a kivétellel, hogy $\delta$ átmenetfüggvényére $\delta :Q\times \mathcal{R}(\Sigma )\to \mathcal{P}(Q)$ teljesül.

Átmenetdiagramon ábrázolva az általánosítás az, hogy az élek címkéi betűk helyett tetszőleges $\Sigma$ feletti reguláris kifejezések lehetnek.

Legyen $A=⟨Q,\sigma ,\delta ,Q_0,F⟩$ egy általánosított automata és legyenek $u,v\in Q{\Sigma }^{\ast }$ konfigurációk. Az $A$ automata az $u$ szót egy lépésben (közvetlenül) a $v$ szóra redukálja (jelölés: $u⟹Av$), ha van olyan $q,p\in Q,z,w\in {\Sigma }^{\ast },R\in \mathcal{R}(\Sigma )$, hogy $p\in \delta (q,R),z\in L(R),u=qzw$ és $v=pw$ teljesül.

A többlépéses redukció és a felismert nyelv fogalma nem változik.

Az $ϵ$-átmenetes, nemdeterminisztikus véges automata olyan általánosított automata, ahol minden átmenet $\Sigma \cup \{ϵ\}$-beli.

Tehát átmenetfüggvénye az input betűnkénti feldolgozása mellett állapotváltásokat engedélyezhet ($ϵ$-átmenetek).

Kis Bar-Hillel lemma

Minden $L\in {\mathcal{L}}_3$ nyelvhez van olyan $n\in \mathbb{N}$ konstans, hogy minden $w\in L$ szó esetén ha tekintjünk egy tetszőleges olyan $w=u{w}^{\prime }v$ felbontását, ahol $|w^{\prime }|\ge n$, akkor van $w^{\prime }$-nek olyan $y$ részszava $(w^{\prime }=xyz)$, hogy $0<|y|\le n$, és minden $i\ge 0$ esetén $ux{y}^{i}zv\in L$.

Kevésbé formálisan: $L$ minden szavának elég hosszú részszavában létezik elég rövid, nemüres, beiterálható részszava.

Források

• Diasor
• Felvétel

Környezetfüggetlen grammatikák, Chomsky normálforma, CYK algoritmus

• Környezetfüggetlen grammatikák, Chomsky normálforma, CYK algoritmus
  • Redukált grammatika
  • Chomsky normálforma
  • Környezetfüggetlen
  • Források

Egy $G=⟨N,\Sigma ,P,S⟩$ környezetfüggetlen grammatika szabályai $A\to u$ alakúak, ahol $A\in N,i\in (\Sigma \cup N{)}^{\ast }$

Egy $G=⟨N,\Sigma ,P,S⟩$ környezetfüggetlen grammatika egy $X\in N$ nemterminálisát aktívnak mondjuk, ha van olyan $w\in {\Sigma }^{\ast }$ terminális szó, amire $X⟹w$ teljesül. Egyébként $X$-et inaktív nevezzük.

Egy $G=⟨N,\Sigma ,P,S⟩$ környezetfüggetlen grammatika egy $Y\in N$ nemterminálisát elérhetőnek nevezzük, ha léteznek olyan $v_1,v_2\in (N\cup \Sigma {)}^{\ast }$ szavak, amelyekre $S⟹v_{1}Y{v}_2$ teljesül. Egyébként $Y$-t elérhetetlennek (nem elérhetőnek) mondjuk.

Egy $G$ környezetfüggetlen grammatika egy nemterminálisát hasznosnak nevezzük, ha aktív és elérhető. $G$ redukált, ha minden nemterminálisa hasznos.

Redukált grammatika

Minden környezetfüggetlen $G$ grammatikához létezik vele ekvivalens redukált $G^{\prime }$ környezetfüggetlen grammatika.

Lépések:

1. inaktívak elhagyása
2. elérhetetlenek elhagyása

Chomsky normálforma

Egy $G=⟨N,\Sigma ,P,S⟩$ grammatika Chomsky normálformájú, ha minden $P$-beli szabály alakja a következők valamelyike:

• $S\to ϵ$
• $A\to BC,A,B,C\in N$ továbbá $B,C\ne S$, ha $S\to ϵ\in P$
• $A\to a,A\in N,a\in \Sigma$

Minden $G$ környezetfüggetlen grammatikához létezik vele ekvivalens Chomsky normálformájú grammatika

Lépések:

1. álterminálisok bevezetése
2. hosszredukció
3. $ϵ$-mentesítés
4. láncmentesítés

Környezetfüggetlen grammatikák szóproblémája

Legyen $G$ egy környezetfüggetlen grammatika és egy $u\in {\Sigma }^{\ast }$ egy szó. Eldönthető, hogy $u\in L(G)$

A naiv algoritmzs csak exponenciális felső becslést adhatunk a szóprobléma eldöntésének hatékonységéra.

Dinamikus programozás segítségével megalkotott algoritmus már polinomiális lesz.

A CYK algoritmus Chomsky normálformában adott grammatika esetében $|G|\cdot n^3$ nagyságrendűű lépésben eldönti a szóproblémát.

Tetszőleges környezetfüggetlen grammatika esetén tehát a Chomsky normálformára hozással kombinálva a CYK algoritmus hatékonysága $|G{|}^2\cdot n^3$

Források

• Diasor
• Felvétel

9. Veremautomaták

• 9. Veremautomaták
  • Veremautomata konfigurációi
  • Egylépéses redukció
  • Többlépéses redukció és a felismert nyelv
  • Determinisztikus veremautomata
  • Üres veremmel felismert nyelv
  • Végállapottal vs üres veremmel elfogadás
  • Veremautomaták és környezetfüggetlen grammatikák
  • Források

• Input szalag

• Verem

• Véges vezérlő

• A veremautomata a véges automata általánosítása potenciálisan végtelen veremmel és véges kontrollal.

• A verem esetében az új adat mindig a már meglév˝o veremtartalom tetejéhez adódik, kivétele fordított sorrendben történik.

• alapértelmezetten nemdeterminisztikus

A veremautomata egy $A=⟨Z,Q,\Sigma ,\delta ,z_0,q_0,F⟩$ rendezett hetes, ahol

• $Z$ a veremszimbólumok véges halmaza

• $Q$ az állapotok véges halmaza

• $\Sigma$ az inputszimbólumok véges halmaza

• $\delta :Z\times Q\times (\Sigma \cup \{ϵ\})\to {\mathcal{P}}_{v\acute{e}ges}(Z^{\ast }\times Q)$ az úgynevezett átmeneti függvény

• $z_0\in Z$ a kezdeti veremszimbólum

• $q_0\in Q$ a kezdeti állapot

• $F\subseteq Q$ az elfogadó állapotok vagy végállapotok halmaza

• A verem tetején lévő szimbólum, az aktuális állapot és az inputszimbólum együttesen határozzák meg a következő átmenetet.

• Minden lépésben mindenképpen kiveszünk egyetlen egy elemet a verem tetejéről és beteszünk helyette néhányat. (0, 1, 2, $\dots$ darabot)

• Ha $\delta (z,q,\sigma )$ nem üres, akkor ún. $\sigma$-átmenet hajtható végre, ami lehetővé teszi, hogy a veremautomata anélkül változtassa meg az állapotát és/vagy a verem tartalmát, hogy az inputszalagról betűt olvasna be.

• $ϵ$-mozgásra lehetőség van már az első inputszimbólum elolvasása előtt is illetve még az utolsó inputszimbólum elolvasása után is.

Veremautomata konfigurációi

A veremautomata konfigurációja alatt egy $zqw$ alakú szót értünk, ahol $z\in Z^{\ast }$ a verem aktuális tartalma és $q\in Q$ az aktuális állapot és $w\in {\Sigma }^{\ast }$ az input még feldolgozatlan része.

Kezdőkonfigurácicó: $z_0{q}_{0}w$

Egylépéses redukció

Az $A$ veremautomata az $\alpha \in Z^{\ast }Q{\Sigma }^{\ast }$ konfigurációt a $\beta \in Z^{\ast }Q{\Sigma }^{\ast }$ konfigurációra redukálja egy lépésben, amelyet $\alpha ⟹\beta$-val jelölünk, ha létezik olyan $z\in Z,q,p\in Q,a\in \Sigma \cup \{\sigma \},r,u\in Z^{\ast }$ és $w\in {\Sigma }^{\ast }$ , hogy $(u,p)\in \delta (z,q,a)$ és $\alpha =rzqaw$ és $\beta =rupw$ teljesül.

Többlépéses redukció és a felismert nyelv

Az $A$ veremautomata az $\alpha \in Z^{\ast }Q{\Sigma }^{\ast }$ konfigurációt a $\beta \in Z^{\ast }Q{\Sigma }^{\ast }$ konfigurációra redukálja, amelyet $\alpha ⟹\beta$-val jelöljük, ha vagy $\alpha =\beta$, vagy létezik olyan ${\alpha }_1,\dots ,{\alpha }_n$ szavakból álló véges sorozat, ahol $\alpha ={\alpha }_1,\beta ={\alpha }_n$ és ${\alpha }_i⟹{\alpha }_{i+1}$

Az $A$ veremautomata által elfogadó állapottal felismert nyelv: $$L(A)=\{w\in {\Sigma }^{\ast }|z_0{q}_{0}w⟹up,\mathrm{ahol}u\in Z^{\ast },p\in F\}$$

Determinisztikus veremautomata

Az $A$ veremautomatát determinisztikusnak nevezünk, ha minden $(z,q,a)\in Z\times Q\times \Sigma$ esetén $|\delta (z,q,a)|+|\delta (z,q,ϵ)|=1$

Tehát minden $q\in Q$ és $z\in Z$ esetén

• vagy $\delta (z,q,a)$ pontosan egy elemt tartalmaz, minden $a\in \Sigma$ inoutszimbólumra és $\delta (z,q,ϵ)=\varnothing$
• vagy $\delta (z,q,ϵ)$ pontosan egy elemet tartalmaz és $\delta (z,q,a)=\varnothing$ minden $a\in \Sigma$ inputszimbólumra.

Üres veremmel felismert nyelv

Az $A$ veremautomata által üres veremmel felsimert nyelv: $$N(A)=\{w\in {\Sigma }^{\ast }|z_0{q}_{0}w⟹p\mathrm{ahol}p\in Q\}$$

Vegyük észre, hogy ha a verem üres, akkor az automata működése blokkolódik, mivel nincs átmenet definiálva üres verem esetére.

Így a verem az input teljes feldolgozása után, az utolsó átmenettel kell üressé váljon.

Szintén a blokkolás elkerülése végett definiáltuk úgy a kezdőkonfigurációt, hogy a veremábécé egy eleme ($z_0$) már eleve a veremben van.

Az elfogadó állapotok halmaza irreleváns $N(A)$ szempontjából.

Végállapottal vs üres veremmel elfogadás

Bármely $A$ veremautomatához meg tudunk adni egy $A^{\prime }$ veremautomatát, úgy, hogy $N(A^{\prime })=L(A)$ teljesül

Bármely $A$ veremautomatához meg tudunk adni egy $A^{\prime }$ veremautomatát, úgy, hogy $L(A^{\prime })=N(A)$ teljesül

Veremautomaták és környezetfüggetlen grammatikák

Bármely $G$ környezetfüggetlen grammatikához magkonstruálható egy olyan $A$ veremautomata, amelyre $L(A)=L(G)$ teljesül.

Minden $A$ veremautomatához megadható egy környezetfüggetlen $G$ grammatika úgy, hogy $L(G)=N(A)$ teljesül

Források

• Diasor
• Felvétel

10. Levezetési fa - nincs jegyzet

Környezetfüggő grammatikák

• Környezetfüggő grammatikák
  • Kuroda normálforma
  • A környezetfüggő nyelvek szóproblémája
  • Egy 0-típusú normálforma
  • Források

Egy $G=⟨N,\Sigma ,P,S⟩$ grammatikát hossz-nemcsökkentőnek mondunk, ha minden szabályának alakjára az alábbiak valamelyike teljesül:

• $S\to ϵ$, de ha van ilyen szabály, $S$ nem lehet szabály jobb oldalán
• $u\to v$, ahol $u,v\in (\Sigma \cup N{)}^{+}$ és $|u|\le |v|$

Minden hossz-nemcsökkentő grammatika környezetfüggő nyelvet generál.

Következmény: ${\mathcal{L}}_2\subset {\mathcal{L}}_1$

Kuroda normálforma

Egy $G$ grammatikát Kuroda normálformájúnak mondunk, ha minden szabályának alakjára az alábbiak valamelyike teljesül:

• $S\to ϵ$, de ha van ilyen szabály, $S$ nem lehet més szabály jobb oldalán.
• $A\to a$
• $A\to BC$
• $AB\to AC$
• $BA\to CA$

Minen környezetfüggő $G$ grammatikához van vele ekvivalens Kuroda normálformájú $G^{\prime }$ grammatika.

A környezetfüggő nyelvek szóproblémája

Eldönthető, egy $G$ hossz-nemcsökkentő grammatika és $u\in {\Sigma }^{\ast }$ szó esetén $u\in L(G)$.

Egy 0-típusú normálforma

Bármely $G$ 0-típusú grammatikához van vele ekvivalens $G^{\prime }$ grammatika, ahol $G^{\prime }$ minden szabályának alakjára az alábbiak valamelyike teljesül:

• $S\to ϵ$, de ha van ilyen szabály, $S$ nem lehet más szabály jobb oldalán.
• $A\to a$
• $A\to B$
• $A\to BC$
• $AB\to B$
• $AB\to AC$
• $BA\to CA$

Források

• Diasor

12. Előadás - nincs jegyzet

A számításelmélet alapjai I. gyakorlat

Alapadatok

Idő: Szerda, 10:00 - 12:00
Helyszín: Déli Tömb 00-115
Oktató: Tichler Krisztián
Csoport: 2

Értékelés

• 2 ZH, egyet lehet javítani

Források

• Canvas

Nyelvek

• Előadás ismétlése
• Előadás példáihoz hasonló feladatok.

Források

• Segédanyag - pdf
• Felvétel
• Órán készült rajzok

Grammatikák

Grammatikák megadása, generált nyelv meghatározása.

Források

• Segédanyag - pdf
• Felvétel
• Órán készült rajzok

Elmaradt óra

Ez az óra elmaradt, és nem tartottak pótló órát.

Grammatikák II

Források

• Grammatikák feladatsor
• Felvétel
• Órán készült rajzok

Grammatikák III, reguláris kifejezések

Források

• Grammatikák feladatsor
• Reguláris kifejezések feladatsor
• Felvétel
• Órán készült rajzok

Véges automaták

Források

• Véges automaták feladatsor
• Felvétel
• Órán készült rajzok

Zárthelyi

ZH megoldás, grammatikák visszamenőleg, általános automaták

Források

• Feladatsor
• Felvétel
• Órán készült rajzok

9. Általános automaták, Chmosky normálforma, CYK algoritmus

Források

• Feladatsor
• Felvétel
• Rajzok

Veremautomaták

Források

• Felvétel
• Rajzok
• Segédanyag

11. Gyakorlat - nincs jegyzet

Adatbázisok I. előadás

Alapadatok

Idő: Kedd, 12:00 - 14:00
Helyszín: Déli Tömb 0-821 Bólyai János terem
Oktató: Szalai-Gindl János Márk, szalaigindl@inf.elte.hu
Csoport: 2

Értékelés

• Írásbeli vizsga
  • Ehhez lehalább 2-es gyakorlatjegy szükséges
  • Elméleti és gyakorlati feladatok
  • Beugró Canvason jelenlétben, aztán hosszabb, esszé jellegű feladatok

Források

• Canvas
• Tankönyv

Bevezetés és relációs adatmodell

• Bevezetés és relációs adatmodell
  • Mi az az adatbázis?
    • Példa: egyetemi oktatás
      • Nyers fájlok
        • Adatintegritás
        • Implementáció
        • Tartósság
    • Adatbázis definiálása
  • Adatmodell fogalma
  • Relációs adatmodell
    • Megszorítás
  • Algebra
    • Relációs algebra
  • Források

Mi az az adatbázis?

Hátköznapi értelemben: összefüggő adatok praktikusan rendezett gyűjteménye és ezeknek valamilyen rendszerben való tárolása, amely a való világot valamilyen szempontból modellezi.

Adathalmaz $\ne$ adatbázis.

Ma már az élet számos területén alapvető fontossággal bírnak.

Példa: egyetemi oktatás

Tegyük fel, hogy egy olyan adatbázist szeretnénk, amely az egyetemi oktatásról készít modellt.

A dolgok, amelyeket tárolnunk kell:

• Infók az oktatókról
  • azonosítószám
  • név
  • beosztás
• Tárgyakról
  • név
  • oktató azonosító
  • bevezetés éve
• Termek használatáról
  • épület
  • szobaszám
  • időköz
  • tárgynév

Egy tárgyat egy vagy több oktató oktathat, egy oktató egy vagy több tárgyat oktathat.

Egy időben egy teremben csak egy tárgyat oktathatnak.

Nyers fájlok

Tároljuk az adatokat CSV fájlokban.

Használjunk egy-egy fájlt az oktatóra, a tárgyakra és a teremhasználatra!

Az alkalmazásunknak majd szintaktikai elemzést kell végezni minden egyes alkalommal a fájlokon, amikor olvasni/frisséteni fogja a bejegyzéseket.

Adatintegritás

Hogyan tudjuk azt biztosítani, hogy egy előadó az összes albumánál ugyanabban a formában jelenjen meg?

• Pl. adatbázis, adatbázisok, AB, $\dots$

Mi történik, ha valaki véletlenül felülírja a tárgy bevezetésének évét egy érvénytelen stringgel?

• Pl. 1993 helyett ezerkilencszázkilencvenhérom.

Hogyan, milyen formában tároljuk, ha több oktató oktat egy tárgyat?

Implementáció

Hogyan keresünk meg egy adott bejegyzést?

Mi van, ha egy új alkalmazást akarunk készíteni, amelyik ugyanazt az adatbázist használja?

Mi van, ha két thread egyidőben ugyanabba a fájlba próbál írni?

Tartósság

Mi van, a a gép elszáll, miközben éppen egy bejegyzést frissítünk?

Mi van, ha a magas rendelkezésre állás érdekében többszörözni/másolni akarjuk ugyanazt az adatbázist több gépen?

Adatbázis definiálása

Az adatbázisnak új meghatározást adunk: olyan adatok együttese, amelyet egy adatbázis-kezelő rendszer (DBMS: Database Management System) kezel.

Az általános DBMS megoldandó feladatai:

• új adatbázisok létrehozása, ezek logikai szerkezetének, sémájának definiálása, adatdefiníciós nyelv (DDL - Data Definition Language)
• adatok lekérdezése, módosítása (DML - Data Manipulation Language)
• nagyméretű adatok hosszú időn keresztül történő tárolása, adatok biztonsága, meghibásodásokkal, illetéktelen hozzáférőkkel szemben, hatékony adatbázis-hozzáférés
• egyszerre több felhasználó egyidejű hozzáférésének biztosítása

Adatmodell fogalma

Az adatmodell információ vagy adatok leírására szolgáló jelölés.

A leírás részei:

• az adatok struktúrája
• az adatokon végezhető műveletek
• az adatra vonatkozó megszorítások

Legfontosabb modellek: relációs és féligstruktúrált (XML)

Relációs adatmodell

A relációs adatmodellben az adatokat kétdimenziós táblákban (relációkban) tároljuk.

A reláció fejrészében találhatók az attribútomok

Minden attribútomhoz hozzátartozik egy értékkészlet

A reláció neve és a reláció-attribútomok halmaza együtt alkotják a relációsémát

A reláció attribútumainak sorrendje felcserélhető.

A séma egy adatmodellben általánosságban azt adja meg, hogy egy-egy adatelem milyen "formájú" adatokat tárol.

Egy-egy reláció soroknak egy halmaza

Halmaz: nem számít a sorrend, egy elem csak egyszer szerepelhet.

A reláció sorainak halmazát előfordulásnak nevezzük.

$\rho \subset X_1\times \cdots \times X_n$ esetén az attribútomok értékkészlete adja az $X_i$ alaphalmazokat ($1\le i\le n$), egy egy előfordulás pedig egy-egy matematikai relációnak "feleltethető meg".

Az attribútumok sorrendje láttuk, hogy nem rögzített a relációsémában. Egy-egy előfordulás ábrázolása esetén viszont rögzítésre kerül.

A lényeg, hogy a soroknál egy attribútum értékét az attribútum nevével azonosítjuk, és nem pedig azzal, hogy hányadik helyen szerepel a soron belül.

Az adatbázis tulajdonképpen relációk halmaza. A megfelelő relációsémák halmaza adja az adatbázissémát, a hozzá tartozó előfordulások pedig az adatbázis-előfordulást.

Egy sor elemeit mezőnek (komponens) nevezzük. Minden mező csak atomi értéket vehet fel. Léteznek bonyolultabb adatmodellek is, ahol egy mező értéke lehet halmaz, lista, tömb, referencia stb.

Megjegyzés: a gyakorlatban sokszor megengedik a sorok ismétlődését, hiszen az ismétlődések megszüntetése nagyon időigényes

Megszorítás

Az attribútumok egy halmaza egy kulcsot alkot egy relációra nézve, ha a reláció bármely előfordulásában nincs két olyan sor, amelyek a kulcs összes attribútumának értékein megegyeznének.

pl. TAJ-szám...

A kulcsot aláhúzás jelöl: Teázó(név, város, tulaj)

Algebra

Egy algebra általában műveleteket és atomi operandusokat tartalmaz.

A relációs algebra lehetővé teszi kifejezések megfogalmazását az atomi operandusokon és az algebrai kifejezéseken végzett műveletek alkalmazásával kapott relációkon.

Fontos tehát, hogy minden művelet végeredménye reláció, amelyen további műveletek adhatók meg.

A relációs algebra atomi operandusai a következők:

• a relációkhoz reprezentáló változók
• konstansok, amelyek véges relációt fejeznek ki

Relációs algebra

• Projekció: Adott relációt vetít le az alsó indexben szereplő attribútumokra.
• Szelekció: Kiválasztja az argumentumban szereplő reláció azon sorait, amelyek eleget tesznek az alsó indexben szereplő feltételnek.
• Unió, metszet, különbség
• Descartes-szorzat
• Átnevezés: relációk adott attribútumanak átnevezése.
• Théta-összekapcsolás: összekapcsolás valamilyen predikátummal
• Természetes összekapcsolás: összekapcsolás predikátum nélkül

Egy relációkon értelmezett operátor akkor monoton, ha bármelyik argumentumrelációhoz egy újabb sort hozzávéve az eredmény tartalmazza az összes olyan sort, amelyet addig tartalmazott és esetleg újabb sorokat is.

Források

• Diasor - Bevezetés
• Diasor - Relációk

Relációs algebra lekérdezések optimizációja és bevezetés az SQL-be

• Relációs algebra lekérdezések optimizációja és bevezetés az SQL-be
  • Relációs algebra lekérdezések optimizációja
    • Algebrai azonosságok
      • Descartes-szorzat és összekapcsolások
      • Projekció és szelekció
      • Kiválasztás és Descartes-szorzat/összekapcsolás
      • Projekció/kiválasztás és halmazműveletek
    • Optimizációs stratégiák
  • Bevezetés az SQL-be
    • A lekérdezés jelentése
      • Információ integráció
      • Minták
      • NULL összehasonlítás
    • Többrelációs lekérdezések
    • Szemantika
      • Formális szemantika
      • Operációs szemantika
    • Explicit sorváltozók
    • Alkérdések
    • Az IN művelet
  • Források

Relációs algebra lekérdezések optimizációja

Cél: a feladatot minél kevesebb adatmozgatással tudjunk megoldani a háttértár és a központi memória között.

• Minél kevesebb disk I/O művelet végrehajtása egy-egy lekérdezés végrehajtása során.
• Az optimalizáció során relációs algebrai azonosságok alkalmazása. ($q\equiv q^{\prime }$)
• Eredetivel ekvivalens lekérdezés készítése, kiszámításához az esetek többségében kevesebb I/O művelet

Algebrai azonosságok

Descartes-szorzat és összekapcsolások

Projekció és szelekció

Kiválasztás és Descartes-szorzat/összekapcsolás

Projekció/kiválasztás és halmazműveletek

Optimizációs stratégiák

• Feltételek darabolása és letolása (minél előbb szűrjünk)
• Projekciók letolása (projektáljunk minél előbb)
• Utolsó lépésként ${\prod }_L({\sigma }_c(R\times S)),\sigma (R\times S)$ kifejezések helyettesítése természetes összekapcsolással, $\theta$-összekapcsolással.

Ha diszjunkciók is megjelennek, azok nehezíthetik a lekérdezések optimalizációját.

Bevezetés az SQL-be

Az SQL magas szintű programozási nyelv.

Az adatbázis-kezelő rendszer kitalálja a leggyorsabb végrehajtási módot.

  SELECT -- az érdekes attribútumok
  FROM -- egy vagy több tábla
  WHERE -- a táblák soraira vonatkozó feltételek
  AS -- átnevezés
  LIKE -- mintaillesztés
  IN -- eleme

A lekérdezés jelentése

• Kezdjük a FROM záradékban megadott relációval.
• Alkalmazzuk a WHERE záradékban megadott kiválasztási feltételt.
• Levetítjük az eredményt a SELECT záradékban megadott oszlopokra.

A SELECT záradékban megjelenhet algebrai kifejezés, például:

  SELECT teázó, tea, ár*114 AS árJenben
  FROM Felszolgál

Információ integráció

• Sokszor az adatbázisokat sok forrásból építik fel (adattárházak).
• Tegyük fel, hogy minden teázónak van egy saját Menü(tea, ár) táblája.
• A Felszolgál(teázó, tea, ár) tábla elkészítéséhez minden ilyen táblát fel kell dolgoznunk és a teázó nevét konstansként kell beszúrnunk.

Például Joe teázója esetében ezzel a lekérdezéssel dolgozhatunk:

  SELECT ’Joe teázója’, tea, ár
  FROM Menü;

A WHERE zárdékában logikai kifejezéseket is használhatunk.

Minták

A feltételekben a sztringeket mintákra illeszthetjük a LIKE kulcsszóval.

Minta aposztrófok közötti szöveg az alábbi jelekkel: % = “akármennyi karakter”; _ = “tetszőleges karakter, pontosan egy.”

Például:

  SELECT név
  FROM Vendégek
  WHERE cím LIKE '%Budapest%';

NULL összehasonlítás

Az SQL valójában 3-értékű logikát használ: TRUE, FALSE, UNKNOWN.

Ha egy értéket (NULL értéket is beleértve) NULL-lal hasonlítunk, az eredmény UNKNOWN.

Egy sor akkor és csak akkor kerül be az eredménybe, ha a WHERE záradék TRUE értéket ad.

Többrelációs lekérdezések

Általában több táblából kell kinyernünk az adatokat.

Ekkor a relációkat a FROM záradékban kell felsorolnunk.

Az azonos attribútum neveket az alábbi módon különböztetjük meg egymástól:
<reláció>.<attribútum> .

Példa:

  SELECT tea
  FROM Szeret, Látogat
  WHERE teázó = 'Joe teázója' AND
  Látogat.vendég = Szeret.vendég

Szemantika

Formális szemantika

Majdnem ugyanaz, mint korábban:

1. Vegyük a FROM záradékban szereplő relációk Descartes-szorzatát.
2. Alkalmazzuk a WHERE záradék feltételét.
3. Vetítsünk a SELECT záradék oszlopaira.

Operációs szemantika

Képzeljük úgy, mintha minden FROM záradékbeli táblához tartozna egy sorváltozó.

• Ezekkel a sorok összes lehetséges kombinációját vesszük.
• Ha a sorváltozók a WHERE záradékot kielégítő sorra mutatnak, küldjük el ezeket a sorokat a SELECT záradékba.

Explicit sorváltozók

Esetenként egy tábla több példányára is szükségünk van.

• A FROM záradékban a relációk neve után adjuk meg a hozzájuk tartozó sorváltozók nevét.
• Egy relációt mindig átnevezhetünk ily módon, akkor is, ha egyébként nincs rá szükség.

Példa: önmagával vett összekapcsolás

  SELECT b1.név, b2.név
  FROM Teák b1, Teák b2
  WHERE b1.gyártó = b2.gyártó AND
        b1.név < b2.név;

Alkérdések

A FROM és WHERE záradékban zárójelezett SELECT-FROM-WHERE utasításokat (alkérdés) is használhatunk.

Példa: a FROM záradékban a létező relációk mellett, alkérdéssel létrehozott ideiglenes táblát is megadhatunk.

• Ilyenkor a legtöbb esetben explicite meg kell adnunk a sorváltozó nevét.

  SELECT tea
  FROM Szeret, (SELECT vendég
    FROM Látogat
    WHERE teázó = 'Joe teázója')JD
  WHERE Szeret.vendég = JD.vendég;

Az IN művelet

• <sor> IN (<alkérdés>) igaz, akkor és csak akkor, ha a sor eleme az alkérdés eredményének.
• Tagadás: <sor> NOT IN (<alkérdés>).
• Az IN-kifejezések a WHERE záradékban jelenhetnek meg.

Példa:

  SELECT *
  FROM Teák
  WHERE név IN (SELECT tea
                  FROM Szeret
                  WHERE vendég = 'Fred');

Források

• Diasor - Relációs algebra lekérdezések optimizációja
• Diasor - SQL bevezetés I - pdf
• Diasor - SQL bevezetés II - pdf

SQL Bevezetés folytatás, haladó SQL

• SQL Bevezetés folytatás, haladó SQL
  • Bevezetés az SQL-be II
    • Az EXIST művelet
    • Az ANY művelet
    • Az ALL művelet
    • Unió, metszet, különbség
    • Ismétlődések kiküszöbölése
    • Összekapcsolás kifejezések
      • Theta összekapcsolás
    • Relációs algebra és az SQL
  • Haladó SQL
    • Összekapcsolás típusok
      • Belső összekapcsolások
      • Külső összekapcsolás
    • Összesítések
    • Csoportosítás
    • Adatbázis módosítások
      • Beszúrás
        • Default értékek megadása
        • Több sor beszúrása
      • Törlés
      • Módosítás
    • Adatbázis sémák SQL-ben
      • Relációk létrehozása
        • Kulcsok megadása
        • PRIMARY KEY vs UNIQUE
      • Relációk törlése
  • Források

Bevezetés az SQL-be II

Az EXIST művelet

EXIST(<alkérdés>) akkor és csak akkor igaz, ha az alkérdés eredménye nem üres.

  SELECT *
  FROM Teák b1
  WHERE NOT EXISTS (
    SELECT * 
    FROM Teák
    WHERE gyártó = b1.gyártó AND 
          név != b1.név
  );

Az ANY művelet

x = ANY(<alkérdés>) akkor és csak akkor igaz, ha x egyenlő az alkérdés legalább egy sorával

Az ALL művelet

x != ALL(<alkérdés>) akkor és csak akkor igaz, ha x az alkérdés egyetlen sorával sem egyezik meg.

  SELECT tea
  FROM Felszolgál
  WHERE ár >= ALL(
        SELECT ár
        FROM Felszolgál
  );

Unió, metszet, különbség

(<alkérdés>)UNION/INTERSECT/MINUS(<alkérdés>)

  (SELECT * FROM Szeret)
  INTERSECT
  (
    SELECT vendég, tea
    FROM Felszolgál, Látogat
    WHERE Felszolgál.teázó = Látogat.teázó
  );

A SELECT-FROM-WHERE multihalmaz szemantikát használnak, a halmazműveleteknél mégis a halmaz szemantika érvényes.

Ismétlődések kiküszöbölése

DISTINCT kulcsszó.

Összekapcsolás kifejezések

Az SQL-ben számos változata megtalálható az összekapcsolásnak.

Ezek a kifejezések önmagukban is állhatnak lekérdezésként, vagy a FROM zátadékban is megjelenhetnek.