Kihagyás

1. gyakorlat

16:00-kor kezdünk!

Formális nyelvek és fordítóprogramok alapjai

  • Formális nyelvek
  • fordítóprogramok

Formális nyelvek és fordítóprogramok

Mindig lesz hívás Team-en (nincs jelenléti ív)

  • 2 ZH (1-1 a témakörökből)
  • Jegy: két ZH átlaga
    • ZH 30 pontos
  • Feladatgyűjtemény Teams-en
  • Lesznek szorgalmi feladatok ebből

Bevezetés

ábécé: Jelek egy nem üres, véges halmaza

betű: az ábécé elemei

szó: Egy \(V\) ábécé elemeinek véges sorozata \(\rightarrow\) \(V\) feletti szó (\(V^*\))

\(\varepsilon\): 0 hosszúságú szó

Nyelv: \(V^*\) valamely részhalmaza, a \(V\) ábécé feletti nyelv. Jele: L

  • \(L \subseteq V^*\)

Lexikografikus rendezés:

  • Szavak rendezése hossz szerint
  • Azonos hosszúságú szavak rendezése a jól ismert ábécé rendezés szerint

Konkatenáció: összefűzés (egymás mögé írjuk a két szót dah)

Feladat (fgy/1.)

Megfordítással és konkatenációval létrehozva az alábbiakat az alábbiakból

aabcd, dcba, aa, 321b2, b123, b2, aab2, 321321b321, 123, abc, dcbaaaaaabcd

aa + b2 = aab2

dcba + aa + aa + rev abcd = dcbaaaaaabcd

123 + b2 = 123b2

dcbaaaaaabcd = dcba + aa + aa + rev(dcba)

321b2 = rev(123) + b2

321321b321 = rev(123) + rev(b123) + rev(123)

dcbaa + aa + aabcd

Második feladat +0.5 pont

Sorolja fel az összes, legfeljebb 6 hosszú szót, ami az alábbi kettőből előállítható összefűzés (konkatenáció) és megfordítási műveletek segítségével!

😛😬, 😍😷🙂

További alapfogalmak

  • Részszó: a \(v\) részszava \(u\), ha van olyan \(w_1\) és \(w_2\) szavak, hogy \(u = w_1 \; v \; w_2\) - Valódi résszó, ha \(v \neq u\) és (\(w_1 \neq \varepsilon\) vagy \(w_2 \neq \varepsilon\))
  • Szó prefixe: A \(v\) az \(u\) szó prefixe, ha van olyan \(w\) szó, hogy \(u = vw\).
    • Valódi prefix, ha \(v \neq \varepsilon\) és \(v \neq u\).
  • Szó suffixe: A \(v\) az \(u\) szó suffixe, ha van olyan \(w\) szó, hogy u = wv.
    • Valódi suffix, ha \(v \ne \varepsilon\) és \(v \ne u\).

Feladat (fgy/3.)

Legyen \(V = \{a, b, c\}\) és legyen \(u1 = cca\), \(u2 = aabc\) egy–egy \(V\) feletti szó. Soroljuk fel u1 és u2 valódi részszavait, adjuk meg a hosszukat, konkatenáltjukat, tükörképüket, 0-adik, 1., 2. és 3. hatványukat!

\(u_1\) valódi részszavai: c, a, cc, ca, cca

\(|u_1| = 3\)

\(|u_2| = 4\)

\(u_1\) + \(u_2\) = ccaaabc

\(u_1^{-1}\) = acc (ez a fordított)

\(u_2^{-1}\) = cbaa (ez a fordított)

\(u_1^0 = \varepsilon\)

\(u_1^1 = \text{cca}\)

\(u_1^2 = \text{ccacca}\)

\(u_1^3 = \text{ccaccacca}\)

\(u_2^0 = \varepsilon\)

\(u_2^1 = \text{aabc}\)

\(u_2^2 = \text{aabcaabc}\)

\(u_2^3 = \text{aabcaabcaabc}\)

\(u_2\) valódi részszavai: a, b, c, aa, ab, bc, aab, abc, aabc

Feladat (fgy. 4)

\(\varepsilon\) = ""

{\(\varepsilon\), a, c, x, ba, ca, xy, yx, abc, bca, bxyz, xabc}

Feladat (fgy. 6)

Adja meg az alábbi két nyelv egyesítését (unióját), összefűzését (konkatenációját) és metszetét!

{@#, !%%}, {&@, @#, !%}

Unió: {@#, !%%, &@, !%} (hagyományos unió művelet)

Metszete: {@#} (hagyományos metszet művelet)

Konkatenációja: ???

\(L \subseteq V^*\) nyelv komplementere: \(\overline L = V^* \setminus L\) Két nyelv konkatenációja:

Gyakorlatilag egy Descartes szorzat

\(L_1L_2 := \{uv | u \in L_2 \land v \in L_2\}\)

\(\{\varepsilon\}L = L = L\{\varepsilon\}\)

\(L\emptyset=\emptyset=\emptyset L\)

LG = [l + g for l in L for g in G] Nyelv tükörképe a szavak tükörképe

\(L^{-1} := \{u \in V^* | u^{-1} \in L\}\)

Az üres nyelv és az egy üres elemet tartalmazó nyelv nem ugyanaz!

Üres elemet tartalmazó nyelv: {\(\varepsilon\)}

Üres nyelv: {}

nyelv hatványa

A 0. hatvány az 1 db üres elemet tartalmazó nyelv

Az 1. hatvány a nyelv önmaga

feladat (fgy. 6 (megint))

Konkatenációja: {@#&@, @#@#, @#!%, !%%&@, !%%@#, !%%!%}

amongusamonguamongus :sus: ඞඞ

Feladat (fgy / 7.)

Adja meg az alábbi nyelv nulladik, első, második és harmadik hatványát!

{x, xy, yyx} = L

\(L^0 = \{\emptyset\} \; \text{vagy} \; \{\varepsilon\}\)

\(L^1 = L = \{x, xy, yyx\}\)

\(L^2 = L^1L = \{xx, xxy, xyyx, xyx, xyxy, xyyyx, yyxx, yyxxy, yyxyyx\}\)

\(L^3 = L^2L = \{xxx , xxxy, xxyyx, xxyx, xxyxy, xxyyyx, xyyxx, xyyxxy, xyyxyyx, xyxx, xyxxy, xyxyyx, xyxyx, xyxyxy, xyxyyyx, xyyyxx, xyyyxxy, xyyyxyyx, yyxxx, yyxxxy, yyxxyyx, yyxxyx, yyxxyxy, yyxxyyyx, yyxyyxx, yyxyyxxy, yyxyyxyyx\}\)

Általánosan:

\(L^n := L^{n-1}L\) és

\(L^0 = \{\varepsilon\}\)

which insane person did \(L^3\) lmao ඞ (Boxy did)

Feladat (fgy. 9.)

Melyik nyelv(ek)nek a második hatványa a {\(\varepsilon\), 0, 1, 00, 01, 10, 11, 100, 010, 101, 110, 1010}?

\(L^0\) = {\(\varepsilon\)}

\(L^1 = L\) = {\(\varepsilon\), 0, 1, 10}

\(L^2 = LL\) = {\(\varepsilon\), 0, 1, 10, \(0\), 00, 01, 010, \(\red 1\), \(\red 10\), 110, \(\red 10\), 100, 101, 1010} = {\(\varepsilon\), 0, 1, 00, 01, 10, 11, 100, 010, 101, 110, 1010}

>>> a = ['', '0', '1', '10']
>>> set([x + y for x in a for y in a])
{'', '00', '010', '10', '110', '0', '1', '11', '101', '1010', '100', '01'} # somethings not right? no, it's fine. I think. Csak nincs lexikálisan rendezve ohhhh

a = ["", "0", "1", "10"]
[x ++ y | x <- a , y <- a]
["","0","1","10","0","00","01","010","1","10","11","110","10","100","101","1010"]
-- oh wait i have repeating

Nyelv lezártja

Fogjuk az összes hatványát, és uniózzuk őket

\(L^* = \bigcup\limits_{i \ge 0} L_i\)

Illetve

\(L^+ = \bigcup\limits_{i \ge 1} L_i\)

Feladat (fgy. 11)

Adja meg az alábbi nyelvek lezártját! (Legfeljebb 6 hosszú szavak)

  • {}
  • {\(\varepsilon\)}
  • {a}
  • {x, yz}
  • \(\{\}^* = \{\varepsilon\}\)
  • \(\{\varepsilon\}^* = \{\varepsilon\}\)
  • \(\{a\}^* = \{\varepsilon, a, aa, aaa, aaaa, aaaaa, aaaaaa, \dots\}\)
  • \(\{x, yz\}^* = \{\varepsilon, x, yz, xx, yzyz, xxx, xyz, yzx, xxxx, xxyz, xyzx, yzxx, xxxxx, xxxyz, xxyzx, xyzxx, yzxxx, yzxyz, yzyzx, xxxxyz, xxxyzx, xxyzxx, xyzxxx, xyzxyz, xyzyzx, yzxxxx, yzxxyz, yzxyzx, yzyzxx\}\)

Feladat (fgy / 8.) (szorgalmi, +1 pontért)

Adjon meg olyan nyelveket, amelyeknek második hatványa egyenlő önmagukkal!

Hány ilyen tulajdonságú véges nyelv van?

Tehát, ahol \(L^2 = LL\)

Ha \(L = \{\varepsilon\}\)

\(L^0 = \{\varepsilon\}\)

\(L^1 = L = \{\varepsilon\}\)

\(L^2 = LL = \{\varepsilon\}\)