# Formális nyelvek és fordítóprogramok (IP-18bFNYFPRG)

## Tartalomjegyzék

<!-- TOC -->
- [Tartalomjegyzék](#tartalomjegyzék)
- [Meta](#meta)
- [Bevezetés a formális nyelvekbe](#bevezetés-a-formális-nyelvekbe)
  - [Alapfogalmak](#alapfogalmak)
    - [Ábécé](#ábécé)
    - [Szó](#szó)
    - [Nyelv](#nyelv)
  - [Feladatok](#feladatok)
<!-- /TOC -->

## Meta

- Gyakvez: Mácskovity Máté
  - Csak Teamset néz!! Lehet tegezni
  - Elnézést kér a stílusáért, 11.eseket (és ovisokat és nyugdíjasokat) tanít
  - gay lol
- 4\. hiányzást meg lehet beszélni, utána nem enged át
  - Papír ass katalógus
- Min. 33% Mindkét zh külön, az átlaguk min. 40%
  - Csak ebből áll a pont
  - Ponthatárok:
    - 2: >= 40%
    - 3: >= 55%
    - 4: >= 70%
    - 5: >= 85%
- Két részből áll a félév
  1. Formális nyelvek
      - Első zh papíron, elmélet
  2. Fordítóprogramok
      - Második zh gépteremben, gyakorlat
- [Saci könyve](https://people.inf.elte.hu/saci/formalis_nyelvek/book.pdf)
- [Hasznos linkek](https://people.inf.elte.hu/veanna/fa/index.htm)

## Bevezetés a formális nyelvekbe

### Alapfogalmak

- Igazából mindegyik tök egyszerű és sose fogsz ránézni ezután

#### Ábécé

Jelölés: $V$[ocabulary]  
Definíció: Betűk véges, nemüres halmaza  
Például: $V_1 = \{a, b, ..., z\}; V_2 = \{0, 1, .., 9\}$

#### Szó

Jelölés: $u$  
Definíció: Véges sorozat $V$ ábécé felett

- *Szó hossza ($l(u)$)*: Sorozat hossza
  - Alternatív jelölés: $|u|$
- *Üres szó* ($\varepsilon$): $l(\varepsilon)$ = 0
- $V_1^*$: $V_1$ ábécé feletti szavak listája
  - $\forall V:\varepsilon\in V^*$
- $V_1^+$: $V_1^* \backslash\{\varepsilon\}$
- *Konkatenáció*: $u, v \in V^*$ esetén a konkatenációjuk $uv$
  - $l(uv) = l(u) + l(v)$
  - Egységelem: $\varepsilon$
  - Asszociatív (tetszőlegesen zárójelezhető)
  - Nem kommutatív
  - $V^*$ konkatenációira nézve zárt
- *Hatványozás*: $u^i(i\in\N)$, ismételt konkatenáció
  - $\forall u: u^0 = \varepsilon$
  - $\forall u: u^1 = u$
  - $(abb)^3 = abbabbabb$
  - stb. stb.
  - **($i$ nem lehet negatív! Tükörképeket sem jelöljük úgy)**
- *Részszó*: $v$ részszava $u$-nak, ha $v = v_1uv_2$
  - *Valódi részszó*: $v \neq \varepsilon$ és $v \neq u$
    - vagyis $0 < l(v) < l(u)$
  - Igen [idiot](https://helyesiras.mta.hu/helyesiras/default/akh12#92), jól írtam
- *Prefix*: $v$-nek prefixe $u$, ha $v = uv_1$
  - *Valódi prefix*: $u \neq \varepsilon$ és $v \neq u$
    - vagyis $0 < l(u) < l(v)$
- *Posztfix*: $v$-nek posztfixe $u$, ha $v = v_1u$
  - *Valódi posztfix*: $u \neq \varepsilon$ és $v \neq u$
    - vagyis $0 < l(u) < l(v)$
- *Tükörkép*: $u^{-1}$, a szó visszafelé
  - **Tulajdonság: $(u^i)^{-1} = (u^{-1})^i$**

#### Nyelv

Jelölés: $L$[anguage]  
Definíció: Szavak halmaza ($L \subseteq V^*$)

- Lehet *véges* és *végtelen* (értelemszerűen)
- *Halmaz hossza*: $|L|$
  - Végtelen halmaz végtelen... $\left|L\right| = \infty$
- *Üres nyelv*: $\emptyset$
  - **(!!)** $\varnothing \neq \varepsilon$
  - **(!!)** $\emptyset \neq \{ \varepsilon \}$
- *Unio*: $L_1 \cup L_2 = \{ u\ |\ u \in L_1 \lor u \in L_2 \}$
- *Metszet*: $L_1 \land L_2 = \{ u\ |\ u \in L_1 \land u \in L_2 \}$
- *Különbség*: $L_1 \backslash L_2 = \{ u\ |\ u \in L_1 \land u \notin L_2 \}$
- *Komplementer*: $V$ ábécére nézve $\overline{L} = V^* \backslash L$
- *Nyelvek konkatenációja*: $L_1L_2 = \{ uv\ |\ u \in L_1 \land v \in L_2 \}$
  - Első nyelv összes szava konkkatenálva második nyelv összes szavával (ilyen sorrendben)
  - Figyeljünk az ismétlődésekre
- *Nyelv hatványozása*: Nyelv ismételt konkatenációja önmagával
  - **(!!)** $\forall L: L^0 = \{ \varepsilon \} $
    - **(!!)** $\varnothing^0 = \{ \varepsilon \}$
- *Iteratív lezárt*: $L^* = \bigcup_{i \geq 0} L^i$
  - [Kleene closure](https://notesread.com/kleene-closure/)
  - **Nem összekeverendő $V^*$-al**
- *Pozitív lezárt*: $L^+ = \bigcup_{i \geq 0} L^i$
  - **Nem összekeverendő $V^+$-al** (és $L^*$-al)

### Feladatok

1. Egyszerű feladatok nyelvekre
    - Definíciók
      - $L_1 = \{a, bb, aba \}$
      - $L_2 = \{ (ab)^n\ |\ n \geq 0 \}$
      - $L_3 = \{ u \in \{ a, b \}^*\ |\ l_a(u) = l_b(u) \}$
      - $L_4 = \{ u \in \{ a, b \}^*\ |\ l_b(u) \mod{2} = 0 \}$  
      - $L_5 = \{ \varepsilon, ba \}$
    - Feladatok
      1. $L_1 \cap L_2 = \{ a \}$
      2. $L_1 \cap L_3 = \varnothing$
      3. $L_1 \cap L_4 = \{ a, bb \}$
      4. $L_2 \backslash L_1 = \{ (ab)^n\ |\ n \geq 1 \}$
      5. $\overline{L_4} = \{ \{ a, b \}^+\ |\ l(b) \mod 2 = 1 \}$
          - Lehetne $\{ a, b \}^*$ is (a $\mod{}$ miatt)
      6. $L_1L_5 = \{ a, aba, bb, bbba, ababa \}$
          - $aba$ nem ismétlődik
      7. $L_1^2 = \{ aa, abb, aaba, bba, bbbb, bbaba, abaa \}$
2. Összetett feladatok nyelvekre
    - Definíciók
      - $L_1 = \{ a^nb^m\ |\ m \geq n \geq 0 \}$
      - $L_2 = \{ ab \}^*$
    - Feladatok
      1. $L_1 \cap L_2 = \{ \varepsilon, ab \}$
      2. $L_1 \backslash L_2^* = L_1 \backslash L_2 = L_1 \backslash \{ \varepsilon, ab\} = \{ a^nb^m\ |\ m \gt n \geq 0 \lor m = n \geq 2 \}$
      3. $L_2 \backslash L_1^* = \varnothing$