Twierdzenie Scotta

Poniżej przedstawię Ci treść i dowód twierdzenia o determinizacji automatów skończenie stanowych, znanym mi pod nazwą "Twierdzenia Scotta".

Treść twierdzenia

Twierdzenie Scotta o determinizacji niedeterministycznych automatów skończenie stanowych mówi, że dla każdego niedeterministycznego automatu skończenie stanowego istnieje taki deterministyczny automat skończenie stanowy , że .

Continue reading »

Lemat o pompowaniu dla języków regularnych

Przedstawię Ci tutaj treść i dowód lematu o pompowaniu dla języków regularnych. Zakładam, że znasz podstawowe definicje takie jak DFA czy rozszerzona funkcja przejścia dla DFA.

Twierdzenie

Niech , gdzie jest deterministycznym automatem skończenie stanowym. Istnieje wówczas taka liczba naturalna , że dowolne słowo , (jest niekrótsze od ) można przedstawić w postaci konkatenacji takich słów  ), że:

  1. ,
  2. ,
  3. słowo .
Continue reading »

DANI2 - Definicje

Miałem ostatnio chwilę czasu i sporządziłem następującego PDFa:

Analiza matematyczna dla informatyków 2 - Definicje .

Zawarte w nim są wszystkie definicje, których znajomość jest konieczna aby zdać egzamin. Powyższy dokument został oczywiście sprawdzony przez odpowiednie osoby, także nie powinien zawierać większych błędów (ewentualne proszę zgłaszać przez e-mail).

SHA1 pliku w OpenSSL

Potrzebowałem ostatnio SHA1 w OpenSSL, hashować chciałem całe pliki. Oto kod źródłowy:

#include <openssl/sha.h>
#include <stdio.h>
#include <string.h>

char* sha1(char* file_name)
{
    SHA_CTX sha;
    SHA1_Init(&sha);
    FILE* f = fopen(file_name ,"rb");
    char buf[1024];
    int length = 0;
    while((length = fread(buf, 1, 1024, f)))
    {
	SHA1_Update(&sha, buf, length);
    }
    fclose(f);
    unsigned char out[20];
    SHA1_Final(out, &sha);
    return strdup(out);
}