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

<!-- TOC -->
- [Generatív grammatika](#generatív-grammatika)
- [Chomsky generatív grammatika hierarchiája](#chomsky-generatív-grammatika-hierarchiája)
- [Gyakorlatok grammatikákkal](#gyakorlatok-grammatikákkal)
  - [Grammatikák nyelvekből](#grammatikák-nyelvekből)
- [Regex](#regex)
  - [Reguláris műveletek](#reguláris-műveletek)
  - [Reguláris kifejezések ($V$ felett)](#reguláris-kifejezések-v-felett)
    - [Példák](#példák)
- [Házik](#házik)
<!-- /TOC -->

## Generatív grammatika

- Szavakat generál
  - "Szintetizáló eszköz"
  - A szavak összessége egy nyelvet alkot: $L(G)$
- $G = (N, T, P, S)$
  - $N$ - **Nemterminális szimbólumok** halmaza
    - Véges
    - Konvenció: nagybetű
  - $T$ - **Terminális** ábécé
    - Véges
    - Konvenció: kisbetű
    - $\varepsilon \in T$
    - Diszjunkt $N$-től
  - $P$ - **Produkciós szabályok** halmaza
    - Produkciós szabály: $u_1Au_2 \rightarrow B$
      - $u_1, u_2, B \in (N \cup T)^*$
        - $(N \cup T)^*$ elemeit mondatformáknak hívjuk
      - $A \in N$
      - **Levezetés**: Szabályok láncolt alkalmazása ($S \Rightarrow_G^* A$)
  - $S$ - **Kezdőszimbólum**, $S \in N$
- Példa: $G = \{\{S, A, B\}, \{a, b\}, p, S\}$
  - $p$:
    - $S \rightarrow B|bb$
      - $S$-t ki lehet cserélni $B$-re vagy $bb$-re
    - $B \rightarrow aaA$
    - $A \rightarrow a | \varepsilon$
  - Generált szavak:
    - $S \rightarrow bb$
    - $S \rightarrow B \rightarrow aaA \rightarrow aaa$
    - $S \rightarrow B \rightarrow aaA \rightarrow aa\varepsilon$
  - $L(G) = \{ bb, aaa, aa \}$ ($\varepsilon$ eltűnik ha van más is)
- $G$ grammatika alapján generált $L(G)$ nyelvben olyan szavak vannak, ahogy startszimbólumból a nyelv szabályainak (véges?) ismételt alkalmazása után kapunk, és csak terminálószimbólumokból állnak
  - Matekul: $L(G) = \{ u \in T^* | S \Rightarrow_G^* u \}$
- Még több példa
  - $G = \{ \{S\}, \{a\}, \{S \rightarrow aaS | a\}, S \}$
    - $L(G_1) = \{a^{2n + 1} | n \geq 0\}$
  - $S \rightarrow aSb | \varepsilon$
    - $L(G_2) = \{ a^nb^n | n \geq 0 \}$
  - $S \rightarrow ASB | \varepsilon,\, AB \rightarrow BA,\, BA \rightarrow AB,\, A \rightarrow a,\, B \rightarrow b$
    - $L(G_3) = \{ u \in \{a, b\}^* | l_a(u) = l_b(u) \}$

## Chomsky generatív grammatika hierarchiája

- Grammatikák osztályozása különböző feltételek alapján
- Ha valami megfelel egy szintnek, akkor az alatta lévőknek is megfelel
  - Vagyis egyre szigorúbbak
  - $(L_3 \subset L_2 \subset L_1 \subset L_0)$
  - Úgyis csak a legmagasabb érdekel

0. Típus: **Általános** (**mondatszerkezetű**)
    - Nincsen kikötés
1. Típus: **Környezetfüggő**
    - A szabályai $u_1Au_2 \rightarrow u_1Vu_2$ alakúak
      - $u_1, u_2, v \in (N \cup T)^*)$
      - $A \in N$
      - $V \neq \varepsilon$
        - **(!!)** Kivéve ha: $S \rightarrow \varepsilon$
          - DE! ekkor $S$ nem fordulhat elő szabály jobb oldalán
          - **Hossznemcsökkentő!** Ha szabály csökkenti a szó hosszát, az nem 1. típusú grammatika
          - Vizsgakérdés jellegű
    - Példa: $aBaBAbA \rightarrow aBaabBAbA$
      - $u_1 = aBa, u_2 = AbA, A = B, V = abB$
2. Típus: **Környezetfüggetlen** grammatika
    - $A \rightarrow v$
      - $A \in N, v \in (N \cup T)^*$
    - **A programnyelvek is ezzel írhatóak le**
      - Majd előadáson bizonyítjuk
    - Példa
      - $S \rightarrow ab, S \rightarrow AA, B \rightarrow ASa$
3. Típus: **Reguláris** grammatika
    - $A \rightarrow uB$ vagy $A \rightarrow u$
      - $A, B \in N$
      - $u \in T^*$
    - Pl. FSM

## Gyakorlatok grammatikákkal

### Grammatikák nyelvekből

1. 4-gyel osztható bináris számok
    - Egy lehetséges (környezetfüggő) megoldás
      - $S \rightarrow A00\ |\ 0$
      - $A \rightarrow A1\ |\ A0\ |\ 1$
    - Egy lehetséges (reguláris) megoldás
      - $S \rightarrow 1A\ |\ 0$
      - $A \rightarrow 1A\ |\ 0A\ |\ 00$
2. $\{ a^nb^mc^n | n \geq 0, m \geq 3 \}$
    - $S \rightarrow aSc \ |\ bbbB$
    - $B \rightarrow \varepsilon\ |\ bB$

## Regex

### Reguláris műveletek

1. [ $+$ ] - unió (lehet [ $|$ ] )
2. [ $\cdot$ ] - konkatenáció (lehet [ ])
3. [ $*$ ] - lezárás ([iteratív lezárt](./fonya%201.md#nyelv))

### Reguláris kifejezések ($V$ felett)

1. $\varepsilon$
    - elemi reguláris kifejezés
2. $\forall a \in V$
    - elemi reguláris kifejezés - önmaga $a$ illeszkedik rá
3. $R$ reguláris kifejezés esetén $(R)$ is az
4. $R, Q$ reguláris kifejezések esetén:
    1. $Q \cdot R$
        - $Q$ után $R$
    2. $Q + R$
        - ($Q$ vagy $R$ illeszkedik)
    3. $R^*$
      - $R$ iteratív lezártja, duh
      - $R^+$ nem létezik, helyette lehet $RR^*$

#### Példák

- $\{ ab^n | n \geq 0 \}$
  - Generáló reguláris kifejezés: $a \cdot b^*$
- $\{ u \in \{ 0, 1 \} | l_1(u) \geq 1 \}$
  - Generáló reguláris kifejezés: $(0+1)^* \cdot 1 \cdot (0+1)^*$
- */a?/*
  - $\varepsilon + a$
  - *$\varepsilon$-t fogom előre írni, hogy egyértelmű legyen*
- */[0-9]/*
  - $0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9$
- */[^a-z]/*
  - [világ összes karaktere pluszolva]

## Házik

1. $L_1 = \{ u \in \{ c, a \}^*\ |\ \text{u 2. betűje c vagy pontosan 2 db a-t tartalmaz} \}$
    - $\big((a+c) \cdot c \cdot (a+c)^*\big) + \big( c^* \cdot a \cdot c^* \cdot a \cdot c^* \big)$
2. $L_2 = \{ a^{2n+1}b | n \geq 0 \}$
    - $(a \cdot a)^* \cdot a \cdot b$
3. Egész számok
    - Az egyszerűség kedvéért $(0..9) := (0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9)$
      - $(1..9)$, stb. hasonlóan
    - Regex: */-?\[1-9\]\[0-9\]\*/*
    - $(\varepsilon + -) \cdot (1..9) \cdot (0..9)^*$
4. Valós számok
    - Regex: */-?\[1-9\]\[0-9\]\*(\\.\[0-9\]+)?/*
    - $(\varepsilon + -) \cdot (1..9) \cdot (0..9)^* \cdot \big(\varepsilon + (. \cdot (0..9) \cdot (0..9)^*) \big)$
    - *Itt is (és az egész számoknál is) lehetne engedélyezni $+$-t az elején, de jobb (és olvashatóbb)  így*