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

## Tartalom

<!-- TOC -->
- [Tartalom](#tartalom)
- [Zh információ](#zh-információ)
- [Témák](#témák)
- [Véges Automaták/Generatív izék](#véges-automatákgeneratív-izék)
  - [Overview](#overview)
  - [Típusai](#típusai)
  - [Megadási módjai](#megadási-módjai)
- [Gyártunk dolgokat](#gyártunk-dolgokat)
  - [Lefuttatás](#lefuttatás)
  - [További példák](#további-példák)
<!-- /TOC -->

## Zh információ

- 2 Hét múlva!!! (Ápr. 5, gyak időben)
- Canvas tematika szerint
- Nyilván papíros
- Minden lehet benne amit előtte gyakon vettünk
- Csak csinálj gyakorlófeladatokat lol
- Ha ideges, lehet hogy házi feladatokat rak zhba mert úgyse csinálta meg senki

## Témák

- Analitikus eszközök
- Nyelv "felismerése" automatával

## Véges Automaták/Generatív izék

### Overview

```txt
----------------------
|            |  q_k  |
|            --------|
|                    |
----------------------

---------------------------
| q_0 | a | a | a | a | b |
------^--------------------
      |
olvasófej utolsó q után
```

- $q_k$: állapotváltozó
- **lépéskényszer**
- Minden lépésben egyet megy a szalag
- Az új állapot egy függvénye a régi állapotnak és a beolvasott adatnak
- Elfogadóállapot, vagy nem elfogaddóállapot
- **3-as típusú** (reguláris) nyelveket tud felismerni!!

### Típusai

1. **VA**: Véges Automata

2. **VDA**: Véges Determinisztikus Automata

3. **VNA**: Véges Nemdeterminisztikus automata

    - $\delta \in Q \times T \rightarrow 2^Q$ (hatványhalmaz)
    - több irányba mehetek egy gráfcsúcsból
    - több állapot van a táblázat egy cellájában

### Megadási módjai

1. $A = (Q, T, \delta, q_0, F)$
    - $Q$: Állapotok véges, nemüres halmaza
    - $T$ (lehet $\Gamma$): Inputszimbólumok halmaza ($Q \cap T = \emptyset$)
    - $\delta: Q \times T \rightarrow Q$: Minden érték-állapot párhoz egy új állapothoz rendel
    - $q_0 (\in Q)$: Kezdőállapot
    - $F \subseteq Q$: Elfogadóállapotok **halmaza**
    - Pl.:
      - $A = \big( \{ q_0, q_1, q_2 \}, \{ a, b \}, \delta, q_0, \{q_2\} \big)$
        - $\delta$
          - $\delta(q_0, a) = q_1$
          - $\delta(q_0, b) = q_2$
          - $\delta(q_1, a) = q_0$
          - Többi átmenet nem definiált &rarr; automatikus elutasítás!!

2. Grá**fos** reprezentáció
    - Nem fos
    - Ez az egyetlen amit egyébként használunk
      - De a többi is lesz vizsgán 😭

    ```txt
    (START) --> q_0 ---a---> q_1
                | \____a____/
                |
                b
                |
                |
              |---|
              |q_2| (végállapot)
              |---|
    ```

    - $L(A) 7 {a^{2n}b | n \geq 0}$

3. Táblázatos

    |       |  $a$  |  $b$  |
    | :---: | :---: | :---: |
    | $q_0$ | $q_1$ | $q_2$ |
    | $q_1$ | $q_0$ |       |
    | $q_3$ |       |       |

4. $A = (Q, T, M_\delta, q_0, F)$ (emmdelta)

    - $M_\delta = \{q_0a \rightarrow q_1,$
    - $\phantom{M_\delta = \{}q_1a \rightarrow q_0$
    - $\phantom{M_\delta = \{}q_0b \rightarrow q_2\}$

## Gyártunk dolgokat

- **Kezdőkonfiguráció** ($q_0u$)
  - Prefix: kezdőállapot
  - Szuffix: redukálni kívánt szó
  - Pl.: $q_0aaaab$

### Lefuttatás

$$q_0aaaab
\Rightarrow q_1aaab
\Rightarrow q_0aab
\Rightarrow q_1ab
\Rightarrow q_0b
\Rightarrow q_2 \in F $$

- Eleme az **automata által felismert nyelvnek**
  - $L(A) = \{u \in T^* | q_u \Rightarrow_A^* p, p \in F, q_0 \in Q\}$

### További példák

Grammatika &rarr; gráfolás &rarr; véges automata

0. Figyelem
    - Grammatika:
      - $S \rightarrow aAb$
      - $A \rightarrow aAb | \epsilon$
    - Ez nem 3. típusú!!
    - Nem csinálunk belőle semmit
1. Igazi példa
    - $(a+b)^*a$
    - Nemdeterminisztikus:

      ```txt
      --> q_0 ---a---> q_1
          / \
          ---  (hurokél)
          a, b
      ```

    - Determinisztikusan (ez jobb):

      ```txt
         __b__        __a__
         \   /        \   /
      --> q_0 ---a---> q_1
            \<---b-----/
      ```

2. $1(1+0)^*+0$
    - Nem fogok több `ASCII` gráfot rajzolni mert borzasztóak

3. 3-mal osztható $\N$-beli számok
    - Nem kell foglalkozni a vezető 0-kkal
      - HF: DE IGEN
    - $q_n$: modulo osztályok 3-nak ($n \in \{0, 1, 2\}$)

4. $\N$
    - HF: $\R$

Házi ezeket generatív grammatikával &uarr; meg ilyenek