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

===== Zadanie 1 =====
Opkt.
===== Zadanie 2 =====
===== Zadanie 3 =====
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 4 =====
===== Zadanie 5 =====
http://ii.yebood.com/viewtopic.php?p=100329#100329

===== Zadanie 6 =====
===== Zadanie 7 =====
===== Zadanie 8 =====
Cormen strona 367