# JFiZO

$\newcommand{\N}{\mathbb{N}}$
[TOC]
# Automaty skończone
## Deterministyczne automaty skończone
### Definicje
Deterministyczny automat skończony (ang. Deterministic Finite-state Automaton, DFA) to piątka uporządkowana $<\Sigma, Q, q_0, \delta, F>$, gdzie
- $\Sigma$ jest skończonym alfabetem
- $Q$ jest skończonym zbiorem stanów
- $q_0 \in Q$ jest stanem początkowym
- $F \subseteq Q$ jest zbiorem stanów akceptowanych
- $\delta: \Sigma \times Q \to Q$ jest funkcją przejścia

Intuicyjnie definiujemy $\hat\delta$:

$$
\hat\delta: \Sigma^* \times Q \to Q
$$

Ogólnie mamy na to dwa sposoby:
1) $\hat\delta(aw, q) = \hat\delta(w, \delta(a,q))$
2) $\hat\delta(wa, q) = \delta(a, \hat\delta(w,q))$
zawsze $\hat\delta(\varepsilon,q) = q$

$\hat\delta(w,q)$ to stan w którym jesteśmy po wczytaniu słowa $w$.

Dla automatu $A = <\Sigma, Q, q_0, \delta, F>$ przez $L_A$ oznaczamy język $\{w \in \Sigma^*: \hat\delta(w,q_0) \in F \}$

Język $L$ jest regularny w.t.w gdy istnieje DFA A taki że $L$ = $L_A$.

### Lemat o pompowaniu

Dla każdego języka regularnego $L$ istnieje $k \in \mathbb{N}$ (zwane
**stałą z lematu o pompowaniu**), taka że dla każdego $w \in L$, t. że $|w|
\geq k$ istnieją słowa $x,y,z \in \Sigma*$, takie że $xyz = w, y \neq
\varepsilon$, $|xy| \leq k$ i dla każdego $m \in \mathbb{N}$ zachodzi
$$
xy^mz \in L
$$

:::spoiler Szkic dowodu
Weźmy $k > |Q|$, weźmy dowolne słowo które ma długość większą niż $k$, wtedy z szufladkowej zasady Dirichleta w ciągu stanów przejścia po kolejnych literkach któryś stan się musi powtórzyć.
:::

## Niedeterministyczne automaty skończone
### Definicje
Niedeterministyczny automat skończony (ang. Non-deterministic Finite-state Automaton, NFA) to piątka uporządkowana $<\Sigma, Q, q_0, \delta, F>$, gdzie
- $\Sigma$ jest skończonym alfabetem
- $Q$ jest skończonym zbiorem stanów
- $q_0 \in Q$ jest stanem początkowym
- $F \subseteq Q$ jest zbiorem stanów akceptowanych
:::danger
- $\delta \subseteq Q \times \Sigma \times Q$ jest relacją przejścia (chcemy o niej myśleć jak o binarnej relacji)
:::
Podobnie jak dla automatów deterministycznych definiujemy $\hat\delta$.
$$
\hat\delta \subseteq Q \times \Sigma^* \times Q
$$
$$
<q, \varepsilon, q'> \in \hat\delta \Leftrightarrow q = q'
$$
$$
<q, wa, q'> \in \hat\delta
\Leftrightarrow \exists q'' <q,w,q''> \in \hat\delta \land <q'',a,q'> \in \delta
$$

Dla NFA A,
$$
L_A = \{w\in \Sigma^* | \exists q \in F<q_0,w,q> \in \hat\delta\}
$$
### Automaty niedeterministyczne z epsilon-przejściami
To też piątka uporządkowana. Jedynie zmienia się definicja $\delta$.
:::warning
$\delta \subseteq Q\times (\Sigma \cup \{\varepsilon\}) \times Q$
:::
Za pomocą $\varepsilon$ przejść można zarządać dowolną liczbę stanów początkowych oraz dokładnie 1 końcowy. Jest to bardziej 'ładne' niż jakoś potrzebne.
#### Relacje między DFA i NFA
##### Twierdzenie
Dla każdego NFA $A$ istnieje DFA $A'$, taki że
$L_A = L_A'$.
:::spoiler szkic dowodu
Stan DFA odpowiada podzbiorowi stanów NFA w których aktualnie się 'znajdujemy'.
:::

#### AS na obiektach niebędacych skończonymi słowami
##### Automaty na drzewach (skończonych)
###### Bottom-up
Żuczki są w liściach. Idą do góry, dwa żuczki łączą się w liściu, patrzymy czy żuczek w korzeniu jest zadowolony czy nie.

Czy niedeterminizm coś w tym modelu zmienia?
:::spoiler
Nie :disappointed: (można pokazać, jako ćwiczenia na spacer)
:::

###### Top-down
Żuczek zaczyna w korzeniu, będąc w jakimś wierzchołku robi dwie kopie i każda z nich idzie do dzieci wierzchołka. Żuczek akceptuje gdy wszystkie żuczki w liściach zaakceptują.

Czy niedeterminizm coś w tym modelu zmienia?
:::spoiler
$BottomUpD = BottomUpN = TopDownN \neq TopDownD$

Zbiór drzew nad $\{a,b\}$ w którym jest dokładnie jedno $a$.
Żuczki nie wiedzą co się dzieje na innych poddrzewach.
:::
##### Automaty na słowach nieskończonych
input: $\Sigma ^ \N$

Automat akceptuje słowo $w$ jeśli wczytując $w$ nieskończenie wiele razy znajdzie się w stanie ze zbioru $F$.
#### Zagadka
Czy automaty deterministyczne na słowach nieskończonych rozstrzygają te same języki co automaty niedeterministyczne?

:::spoiler Rozwiązanie
Niech $L$ to język w którym każde słowo ma skończenie wiele jedynek.
Dla takiego języka nie istnieje DFA.
:::spoiler szkic dowodu
Obserwacja: Dla każdego $q\in Q$ osiągalnego ze stanu początkowego istnieje liczba $z(q)$ taka, że $\hat\delta(q, O^{z(q)}) \in F$.

Jak słowo ma jakiś prefiks który dochodzi do $q$, a następnie ma same $0$ to powinno zostać zaakceptowane (musi tak być, ponieważ nieskończenie wiele razy musi być w stanie akceptującym, żeby zaakceptować słowo).

Wystarczy skontruować słowo:
$q_0 | z(q_0) *0 | 1 | q_i | z(q_i)* 0 | \ldots$
Nieskończenie wiele razy pojawi się 1 oraz nieskończenie wiele razy będziemy w stanie akceptującym (sprzeczność).
:::
##### Podzagadka
Czy poprzedni dowód, że DFA umie zrobić to samo co NFA przenosi się na przypadek słów nieskończonych?

## Automaty dwukierunkowe
### Definicje
Ogólnie wszystko tak samo jak DFA tylko $\delta$ to funkcja
$$
\delta: Q \times \Sigma \to Q \times \{L,R\}
$$
Intuicyjnie: przejście z stan, literka do stan, kierunek
### Twierdzenie
Każdy dwukierunkowy automat skończony daje się symulować przez DFA.

:::spoiler
Patrzymy na połączenie dwóch ciągów stanów (czy jest możliwe). Z grubsza jak jest to istnieje ścieżka, więc jest git.

Wszelkie wątpliwości nie są możliwe do skonstruowania.
:::
# Wyrażenia regularne
- $\emptyset$ jest wyrażeniem regularnym i $L_\emptyset = \emptyset$
- $\varepsilon$ jest wyrażeniem regularnym i $L_\varepsilon = \{\varepsilon\}$
- jeśli $a\in \Sigma$ to $a$ jest wyrażeniem regularnym i $L_a = \{a\}$
- jesli $\varphi, \psi$ są wyrażeniami regularnymi to:
- $\varphi+\psi$ jest wyrażeniem regularny i $L_{\varphi+\psi} = L_\varphi \cup L_\psi$
- $\varphi\psi$ jest wyrażeniem regularny i
- $L_{\varphi\psi} = L_\varphi L_\psi = \{wv | w \in L_\varphi,~v\in L_\psi\}$
- $\varphi^*$ jest wyrażeniem skończonym i
- $L_{\varphi^*} = (L_\varphi)^*$

$L^0 = L_{\varepsilon}$

$L^{i+1} = LL^i$

$$
L^* = \bigcup_{i \in \N} L^i
$$
## Twierdzenie
Następujące trzy warunki są równoważne
1. istnieje wyr. regularne $\varphi$, takie że $L_\varphi = L$
2. istnieje DFA $A$, taki że $L = L_A$
3. istnieje NFA z $\varepsilon$-przejściami $A$, taki że $L = L_A$.
:::spoiler szkic dowodu
$3\to 2$ już było

$1\to 3$ konstrukcja NFA tak, żeby było dokładnie jedno wejście i wyjście

$2\to 1$
:::

# Języki bezkontekstowe
## Definicje
- $\Sigma$ - alfabet
- $\pi$ - skończony zbiór par słów nad $\Sigma$, czyli $\pi \subseteq \Sigma^* \times \Sigma^*$

$$
w \longrightarrow_\pi v \Leftrightarrow \exists x,l,r,y \in \Sigma^*,~w = xly,~v=xry,~ <l,r> \in \pi
$$
$\overset{*}{\longrightarrow}_\pi$ - przechodnie (tranzytywne), zwrotne, domknięcie $\longrightarrow_\pi$

$\overset{*}{\longleftrightarrow}$ - równoważnościowe domknięcie $\longrightarrow_\pi$

$\longleftrightarrow_\pi$ - symetryczne domknięcie $\longrightarrow_\pi$
## Gramatyka bezkontekstowa
### Definicja
Gramatyka bezkonteksta, CFG, to $<T, N, S, \pi>$
gdzie $T, N$ to rozłączone alfabety.

- $T$ - symbole terminalne
- $N$ - symbole nieterminalne
- $S$ - symbol początkowy ($S \in N$)
- $\pi \subseteq N \times (T \cup N)^*$ (jest skończone)

$$
\overline{L}_G = \{ w \in (N\cup T)^*: S \overset{*}{\longrightarrow}_\pi w\}
$$
$$
L_G = \overline{L}_G \cap T^*
$$
Język $L$ jest CFL, jeśli istnieje istnieje $G \in CFG,~G = <T,N,S,\pi>$, taka że
$$
L = L_G
$$

#### Znaczenie równości
Jeśli $L_1, L_2 \in CFL$ to napis
$$
L_1 = L_2
$$
oznacza że
$$
L_1 \overset{\cdot}{-} L_2 = \{\varepsilon\}
$$

## Twierdzenie
Każdy język regularny jest CFL.
:::spoiler szkic dowodu
Indukcja strukturalna
:::

## Lemat o pompowaniu dla CFL
Dla każdego języka bezkontekstowego $L$ istnieje stała $n \in \N$ (zwaną stałą z lematu o pompowaniu) dla której $w \in L,~|w| > n$ istnieją 
$s,z,t,y,x \in \Sigma^*$, takie że
$w = sztyx,~zy\neq\varepsilon,~|zty| \le n$, takie że
dla każdego $k \in \N$
$$
sz^kty^kx \in L
$$
:::spoiler szkic dowodu
Patrzymy na gramatykę Chomsky'ego. Z grubsza widać, że to jest pewne drzewo binarne. Rozpatrujemy pewną ściężkę. Musi być na niej powtórzenie jakiegoś stanu. Patrzymy na poddrzewa powtrzającego się stanu.
:::
#### Postać Chomsky’ego gramatyk
CFG, $G = <T,N,S,\pi>$ jest postaci normalnej Chomskyego, gdy każda produkcja z $\pi$ jest albo postaci
$$
A \to BC,~BC \in N
$$
albo
$$
A \to a,~a \in T
$$
##### Twierdzenie
Dla każdej $G\in CFG$ istnieje $G'\in CFG$, takie że $G'$ jest postaci normalnej Chomsky'ego oraz
$$
L_G = L_{G'}
$$
:::spoiler
Dowód został pominięty
:::
## Automaty ze stosem
### Definicja
Automat ze stosem to siódemka uporządkowana $A = <\Sigma, Q, \Gamma, \delta, q_0, S, F>$, gdzie

- $\Sigma$ - skończony alfabet
- $Q$ - skończony zbiór stanów
- $\Gamma$ - skończony zbiór symboli stosowych
- $\delta \subseteq (Q\times (\Sigma \cup \{\varepsilon\}) \times \Gamma ) \times (Q \times \Gamma^*)$
- $q_0$ - stan początkowy
- $S \in \Gamma$ - początkowy symbol stosowy
- $F \subseteq Q$ - zbiór stanów akceptujących

Myślimy w następujący sposób. Zawsze ściągamy jeden element z stosu, a możemy wrzucić wiele.

Ogólnie są dwie konwencje, automat albo akceptuje, gdy stos jest pusty lub
gdy jest w stanie akceptującym. Mając do dyspozycji $\varepsilon$-przejścia
są one równoważne.

#### Twierdzenie

Język jest bezkontekstowy wtedy i tylko wtedy, gdy daje
się rostrzygnąć automatem (niedeterministycznym) ze stosem (NPDA).

#### Wniosek

Przecięcie języka bezkontekstowego i języka regularnego jest bezkontekstowe.

#### Wniosek
Przecięcie dwóch CFL niekoniecznie jest bezkontekstowe. Inaczej mówiąc
automat z dwoma stosami może zdecydowanie więcej niż automat z jednym
stosem.

### Postać Greibach gramtyk bezkontekstowych
CFG $G=<T,N,S,\pi>$ jest w postaci normalnej Greibach, gdy każda produkcja z $\pi$ ma postać 
$$
A \to aw
$$
gdzie $A\in N, a\in T, w \in N^*$
#### Twierdzenie
Dla każdej $G\in$ CFG, istnieje $G'\in$ CFG w postaci normalnej Greibach, taka że
$$
L_G = L_{G'}
$$

# Problemy
## Problemy rekurencyjne
Na początku niech każdy ustali (i nikomu nie mówi, to akurat jest bardzo ważne) jaki jest jego Ulubiony Język Programowania (MUJP).

Język $\subseteq \{0,1\}^*$, albo język $\subseteq \Sigma^*$.
Teraz mamy **problemy**. Problem $\subseteq \N$. (Każdy wie, że $\N = \{0,1\}$.)

Problem $A\subseteq N$ nazywa się **rekurencyjny** albo **obliczalny** albo **rozstrzygalny** gdy istnieje w MUJP program $\phi$, taki że $\forall n \in \N$:
$$
n \in A \Leftrightarrow \phi(n) = 1\\
n \notin A \Leftrightarrow \phi(n) = 0\\
$$

###### obserwacja
Istnieją nierekurencyjne podzbiory $\N$ (argument z kardynalności).

###### obserwacja o problemach rekurencyjnych
Jeśli $A, B$ rekurencyjne to: $A\cup B,~A \cap B,~\overline A$ też.

###### obserwacja
Każdy zbiór skończony jest rekurencyjny.

## Problemy rekurencyjnie przeliczalne (r.e)
Zbiór $A\subseteq N$ jest r.e. gdy istnieje program $\phi_A \in$MUJP, taki że dla każdego $n\in\N$:
$$
\phi_A(n) = 1 \Leftrightarrow n\in A
$$
(dla $n\notin A$ obliczenie $\phi_A(n)$ może się nie zakończyć. Oznaczamy to $\phi_A(n) = \bot$.)

Równoważnie:
$$
\forall n\in\N~\phi_A(n)\in\N \Leftrightarrow n\in A
$$
###### obserwacja
Istnieją zbiory które nie są r.e (argument z kardynalności).

###### obserwacja o problemach r.e
Jeśli $A,B$ są r.e to również $A\cup B,~A\cap B$,

##### Lemat
Jeśli $A, \overline A$ są oba r.e. to są oba rekurencyjne.

#### Twierdzenie
Istnieje bijekcja między $\N$, a programami w MUJP których relacja wejścia-wejścia zawiera się w $\N\times\N$. Ta bijekcja ma być w obie strony efektywna. To znaczy znajać program musimy umieć znaleźć jego numer, a znając numer musimy umieć znaleźć jego program.

#### wniosek
Możemy ustawić programy w ciąg.

$$
K = \{n: \phi_n(n) \in \N\}
$$

:::warning
Nie istnieje efektywna numeracja programów które się zatrzymują.
:::

###### obserwacja
$K$ jest r.e.

## Twierdzenie Touring o nierozstrzygalności problemu stopu
$K$ nie jest rekurencyjny.
:::spoiler Dowód jest niby ważny, więc jest
:::

###### Oznaczenia
$\phi_n$ - program o numerze $n$

$\operatorname{Dom}(\phi_n) = \{m: \phi_n(m)\in \N\}$ (dla każdego $n$ jest to zbiór r.e.).

###### obserwacja
Dla każdego $A\in$ r.e istnieje $n\in\N$, taki że $A = \operatorname{Dom}(\phi_n).$

###### Morał
Zbiory r.e to są "wiersze" w tej tabelce.

$A\in$co-re $\Leftrightarrow~\overline A\in$ r.e

## Funkcje rekurencyjne
$f\subseteq \N\times\N$ nazywa się **częściową funkcją rekurencyjną**, jeśli jest funkcją i jeśli istnieje program $\phi_n$, taki że dla każdego $k\in\N$ zachodzi:
$<k,m>\in f~\Leftrightarrow~\phi_n(k)=m$ (to samo $m$).

### Częściowa funkcja rekurencyjna
Funkcja która wylicza program $\phi_n$ dla jakiegoś $n$.

$\operatorname{Dom}(\phi_n)\subseteq\N$

Podzbiorem zbioru częściowych funkcji rekurencyjnych są **całkowite funkcje rekurencyjne.**
$$
\operatorname{Dom}(\phi_n) = \N
$$

### Definicja relacji
$A,B\subseteq \N$, wtedy $\newcommand{\rek}{\le_{\text{rek}}} A\rek B$ ($A$
jest nie trudniejszy od $B$ w sensie redukcji będącą całkowitą
funkcją rekurencyjną). Gdy istnieje funkcja rekurencyjna $f: \N\to\N$, taka
że
$$
\forall n\in\N~n\in A \Leftrightarrow f(n)\in B
$$
#### obserwacja
Jeśli $A\rek B$ i $B\in$ Rek/r.e, to $A\in$ Rek/r.e.

#### obserwacja 2
Jeśli $A\in$ Rek i $B,\overline B \neq \emptyset$, to
$$
A\rek B
$$

Praporządek - relacja zwrotnia i przechodnia. Z praporządku da się zrobić częściowy porządek poprzez utożsamienie elementów (podzbiorów $\N$) która są w tej samej silnej składowej spójności.

Częściowy porządek, otrzymany z $\rek$ ma element najmniejszy.
Jest to klasa wszystkich zbiorów rekurencyjnych (różnych od $\emptyset$ i $\N$).

#### obserwacja 3
Dla każdego $A\in$ r.e zachodzi
$$
A \rek K
$$
Mówi się, że "$K$ jest r.e - trudny ze względu na redukcję będącą całkowitymi funkcjami rekurencyjnymi."

Ponieważ $K$ jest r.e to mówimy, że $K$ jest r.e-zupełny.

:::warning
Wszystkie dowody nierostrzygalności jakie zobaczymy będą polegały na pokazaniu, że
$$
K\rek A
$$
:::
## Twierdzenie Rice'a
### Definicje
- Podzbiór $A\subseteq\N$ jest trywialny jeśli $A=\N$ lub $A=\emptyset$ wpp jest nietrywialny
- $A\subseteq\N$ jest ekstensjonalny, jeśli dla każdych dwóch $n,m\in\N$ zachodzi implikacja
$$
\forall k\in\N\quad\phi_n(k) = \phi_m(k) \Rightarrow (n\in A \Leftrightarrow m\in A)
$$

### Twierdzenie
Żaden nietrywialny zbiór ekstensjonalny nie jest rozstrzygalny.

Czyli żaden ekstensjonalnej własności programów nie da się automatycznie sprawdzić.

## O naturalnych/kombinatorycznych problemach nierozstrzygalnych
### Thue
$$
Thue = \{<v,w,\pi>: v \overset{*}{\longleftrightarrow}_\pi w\}\\
semiThue = \{<v,w,\pi>: v \overset{*}{\longrightarrow}_\pi w\}
$$
Czy z $v$ da się dojść do $w$ wykonując produkcję ze zbioru $\pi$.

Problem słów dla procesów Thuego / semi-procesów Thuego.
#### Twierdzenie
Thue i Semithue są nierozstrzygalne, ale są r.e.

### Problem odpowiedności Posta
Instacja PCP jest skończony zbiór par słów $P=\{<l_1,r_1>,\ldots,
<l_k,r_k>\}$. Rozwiązaniem $P$ jest słowo $s\in\{1...k\}^{\star}$, takie że
$$
l_{s_1}l_{s_2}\ldots l_{s_m} = r_{s_1}r_{s_2}\ldots r_{s_m}
$$
Problem: Czy dla danego $P$ istnieje rozwiązanie, jest nierozstrzygalny.

## Maszyn Turinga
### Pożegnanie z MUJP
Opierając się tylko na MUJP pokazaliśmy, że $K\notin$ Rek i mnóstwo innych rzeczy, w tym tw. Rice'a.
Teraz się umówimy co do jakiegoś modelu obliczeń.

Były różne koncepcje co do tego jak formalizować pojęcie algorytmu.
- Alonzo Church, $\lambda$-rachunek (obliczalne są funkcje dla których są $\lambda$-termy)
- Stephen Cole Kleene, definiować "najmniejsze klasy które coś tam..., zamknięte na operacje...". Klasa funkcji rekurencyjnych

$\N^k\to \N$
- każda funkcja $f:\N\to\N$ stała jest rek
- $id:\N\to\N$ jest fun rek
- $succ:\N\to\N$ jest fun rek
- każdy rzut na $k$-tą oś jest funkcją rekurencyjną 
Jeśli $g:\N^k\to\N$ jest f rek i $f_1,f_2,\ldots,f_k:\N^m\to\N$ są f rekurencyjną, to $h=g(f_1,f_2,\ldots,f_k)$ jest f rekurencyjną (złożenie) i $h: \N^m\to\N$.

#### Operator rekursji
Jeśli $g:\N^{m+2}\to\N,~h:\N^m\to\N$ są f rek to funkcja
$s:\N^{m+1}\to\N$ zdefiniowana
$$
s(0,w) = h(w)\\
s(k+1,w) = g(k,g(k,s(k,w),w)
$$

#### Operator minimum
Jeśli $g:\N^{m+1}\to\N$ jest rek, to $h:\N^m\to\N$ zdefiniowana jako:
$$
h(w) = \min\{n\in\N: g(n,w) > 0\}
$$
jest rekurencyjna.

### Definicja
- $Q$ stany
- $\Sigma$ alfabet taśmowy
- $\delta:Q\times \Sigma\to Q\times\Sigma\times\{L,R\}$

Jest symbol początkowy $\alpha$, symbol końca wejścia $\omega$, oraz symbole $B$ (blank). Taśma jest potencjalnie nieskończona

Uniwersalna maszyna Touringa.

Bardzo prosty model. Łatwo go zakodować w innych problemach.

### Teza Churcha
Wszystkie modele formalizujące intuicyjne pojęcie algorytmu są równoważne
maszynie Turinga. Wszystkie modele która znamy i wszystkie te które w
przyszłości wymyślimy.