Kihagyás

1. előadás

Egy pár megbeszélni valónk

\(\exists\text{páros}\)

  • Nagy Sára & Dr. Horpácsi Dániel
  • Nagy Sára "mesteroktató"-nak kell írni
    • ha szükséges
    • Ásványi Tibor csak egy báb🤯
  • No food allowed once again...

Elméleti követelmény: nem figyeltem lmao noone did

Algoritmusok és alkalmazásaik

Kapcsolódó tudományágak

  • fordítoprogramok
  • természetes nyelvek gépi feldologozása
  • képfeldolgozás
  • milekuláris számítás (pl. DNS számítás)
  • etc...

Fogalmak

Ábécé: Jelek egy nem üres, véges halmaaza

Betű: Az ábécé elemei

Szó: A \(V\) ábécé elemeinek egy tetszőleges véges sorozatát a \(V\) ábécé feletti szónak nevezzük

Definíciók

  • Ábécé
    • Jelek egy nem üres halmaza
    • Jelölés: \(V\)
  • Betű
    • \(b\in V\)
  • Nyelv
    • \(V^*\) valamely részhalmaza a \(V\) ábécé feletti nyelv
    • Jelölés: \(L\)
    • \(L \subseteq V^*\)
  • Nyelvosztály (nyelvcsalád)
    • Nyelvek valamely csoportja/összessége
  • Szavak konkatenációja
    • Adott \(u=t_1\ldots t_k,\;v=q_1\ldots q_m\in V\)
    • \(uv:=t_1\ldots t_k q_1\ldots q_m\)
    • egyszerű összefűzés
  • Üres szó (String)
    • \(\varepsilon\)
    • \(\varepsilon u=u\)
      • Konkatenáción az egységelem basically
  • Szó hatványa
    • Adott \(u\) szó, nemnegatív egész hatványai:
      • \(u^0:=\varepsilon,\;u^1?=u,\;u^n:=u^{n-1}u\)
  • Szó hossza
    • \(l:V^*\to\N\)
    • Adott \(u=t_1\ldots t_k\) esetén
      • \(l(u):= k\)
  • Részszó (substring)
    • \(v u\)-nak részhalmaza, ha léteznek olyan \(w_1,w_2\), hogy \(u=w_1vw_2\)
    • \(v\) valódi részszó, ha \(v\ne u,\;v\ne\varepsilon\)
  • Szó prefixe
    • \(v\) akkor prefixe \(u\)-nak, ha létezik olyan \(w\), hogy \(u=vw\)
    • valódi prefix, ha \(v\ne\varepsilon,\;v\ne u\)
  • Szó suffixe
    • \(v\) akkor suffixe \(u\)-nak, ha létezik olyan \(w\), hogy \(u=wv\)
    • valódi suffix, ha \(v\ne\varepsilon,\;v\ne u\)
  • Szó megfordítása
    • Jele: \(u^{-1}\)
  • Két nyelv metszete, uniója
    • Megszokott halmazműveletekkel
  • Nyelv komplementere
    • Megfelelő ábécé esetén:
    • Jelőlés: \(\overline{L}=V^*\setminus L\)
  • Két nyelv konkatenációja
    • \(L_1L_2=\{uv\;|\;u\in L_1, v \in L_2\}\)
  • Nyelv hatványa
    • \(L^0:=\{\varepsilon\},\;L^1:=L,\;L^n:=L^{n-1}L\quad(n\ge 1)\)
  • Nyelv lezártja (iteráltja)
    • \(L^*:=L^0\cup L^1 \cup L^2 \cup \ldots\)
    • \(L^+:=L^*\setminus L^0\)
  • Reguláris műveletek:
    • Unió
    • Konkatenáció
    • Lezárás

Reguláris műveletek nyelveken

  • unió
  • konkatenáció
  • lezárás

Nyelv megadási módjai

  • logikai formulával
  • strukturális rekurzióval
  • algoritmussal
  • matematikai géppek
  • produkciós rendszerekkel (szabályokkal)

Programozási nyelvek szintaxisa

Backus-Naur formában (BNF) adják meg

pl.:

<kifejezés> ::= <tag> | <tag> + <kifejezés>
<tag> ::= <faktor> | <faktor> * <tag>
<faktor> ::= i | ( <kifejezés> )

Grammatikák

Négyessel adott: \(G = (N, T, P, S)\)

  • \(N\): Nemterminális ábécé
  • \(T\): terminálisok ábécéje
  • \(P\): átírási szabályok véges halmaza
  • \(S\): kezdőszimbólum

\(N\) és \(T\) diszjunkt

\(S \in N\)

A szabályok \(p \to q\) alakúak, a bal oldalnak kell tartalmaznia legalább egy nemterminális (\(\in N\)) szimbólumot

  • formálisan \(p \in (N \cup T)^*N(N \cup T)^*\)
    • \(q \in (N \\cup T)^*\)

Grammatika által generált nyelv

Minden olyan szó, amely követetten levezethető a kezdőszimbólumból.