====== Algorytmy i struktury danych - Lista 4. ======

===== Zadanie 1 =====
===== Zadanie 2 =====
===== Zadanie 3 =====
===== Zadanie 4 =====
Każdą gramatykę postaci

$A -> a_1....a_ka_{k+1}...a_n$ \\
$A -> a_1$

Da sie sprowadzic do:

$A -> aB$ \\
$A -> bA$ \\
$A -> a$

Wyrazenia typu $A -> B$ mozna w oczywisty sposob zredukowac.

Teraz przechodzimy do algorytmu:

Tworzymy tablice $NxN$ gdzie $N$ to dlugosc slowa.

Jej pola zdefiniowane sa nastepujaco:

$m_{ij}=\{A \in V|A -> a_i...a_j\}$ \\
$m_{ii}=\{A \in V|A -> a_i \}$

Pola $m_{ii}$ wypelniamy automatycznie a $m_{ij}$ wypelniamy wedlug wzoru:

$m_{ij} = a_i m_{i+1,j} \cup m_{i,j-1}a_j$ \\
$a_im_{i+1,j}=\{A \in V| A -> a_iB \land B \in m_{i+1,j}\}$ \\
$m_{i,j-1}a_j=\{A \in V| A -> Ba_j \land B \in m_{i,j-1}\}$ \\ 

===== Zadanie 5 =====
===== Zadanie 6 =====
===== Zadanie 7 =====
===== Zadanie 8 =====
===== Zadanie 9 =====
http://en.wikipedia.org/wiki/Levenshtein_distance

===== Zadania dodatkowe 1. oraz 2. =====
Literatura:
  * http://users.soe.ucsc.edu/~manfred/pubs/J8.pdf
  * http://www.ii.uni.wroc.pl/~lorys/Papers/icalp92.ps