Kihagyás

Nyelvek és definíciók

No food alowed lmao

  • 03.21 : ZH1
  • "Nézegetjük a beat-eket"
  • Potential Canvas quiz
    • quiz \(\ge 80\% \mapsto+1\) point
  • Nagy Sára
    • saci@inf.elte.hu
    • Fogadóóra Csütörtök 2-4 PM
    • EA első felét ő tartja

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

Def - demo

A lexikografikus megadásnál a sorrend számít

Az határozza meg a rendezést a betűk felett a<b<c

\[ V=\{a,b,c\},\;\quad L_1:=\{u\in V\;|\;l_a(u)=1\} \]

\(L_1=\{a,ab,ac,ba,ca,\) \(abb,abc,acb,acc,bab,bac,bba,bca,cab,cac,cba,cca\ldots\}\)

\[ |\{l(u) | u \in L_1, l(u) =3 \}|=12 \]

\(L_2:=\{\in V^*\;|\;l(u)\le 1\}=\{\varepsilon,\;a,\;b,\;c\}\)

\[ \begin{array}c |L_1|=\infty & |L_2|=4 \\ L_3:=\emptyset & |L_3|=0 \\ L_4:=\{\varepsilon\} & |L_4|=1 \\ \end{array} \]

\(u=cca\)

\(L_{\text{prefix}}=\{\varepsilon,c,cc,cca\}\)

\(L_{\text{résszszó}}=L_{\text{prexix}}\cup \{a,ca,\}\)

\[ L_1L_2=\{u_1u_2\in V^*\;|\;u_1\in L_1 \land u_2 \in L_2\} \]

\(L_1=\{a,\;ab\}\)

\(L_2=\{b,\;ab\}\)

\(L_1L_2=\{ab,\;aab,\;abb,\;(ab)^2\}\)

\(L_1^2=L_1L_1=\{aa,aab,aba,abab\}\)

Konklúziók

\[ \{\varepsilon\}L=L \]
\[ \emptyset L= \emptyset \]
\[ L^0 = \{\varepsilon\} \]
\[ \emptyset\cup L = L \]

\(L_1:=\{\varepsilon\}\)

\(L_2=\{a\}\)

\(L_3=\{\varepsilon,\;a\}\)

\[ (L_1\cap L_2)L_3=\emptyset \]
\[ L_1L_3=\{\varepsilon,\;a\} \]
\[ L_2L_3=\{a,\;aa\} \]
\[ L_1L_3 \cap L_2L_3=\{a\} \]

\(L_1:=\{a\}^*\{ba\}^*\)

\(L_2:=\{b^na \;|\;n\ge 0\}\)

  1. \(L_2\cap L_1=\{a,\;ba\}\)
  2. \(L_2\setminus L_1= \{b^na \;|\;n\ge 2\}\)
  3. \(L_2^*\cap L_1^*=L_1^*\)

"Meggondolható" házi feladatok a Canvas-en 😳