Jaskinie Podróże Nurki Grafika Mizar Teksty Kulinaria Lemkov Namiary Mapa RSS English
Spelunka Trybików Mizar Artykuły YAC Software
  Wróć

Mizar

Eddie

Artykuły

Równoważność automatów deter ministycznych i epsilon niedeter ministycznych

Etykietowane systemy tranzycji stanów

Kwantyfikatory w wyrażeniach regularnych - co najmniej m wystąpień

Systemy przepisywania słów

Kwantyfikatory w wyrażeniach regularnych - od m do n wystąpień

Języki formalne - konkatenacja i domknięcie

Boole'owskie właściwości zbiorów

Homomorfizmy i izomorfizmy grup; grupa ilorazowa

Liczby całkowite

Syntaktyka Mizara-MSE

Artykuły
Poniżej znajdują się linki do moich artykułów i tekstów:

Równoważność automatów deter ministycznych i epsilon niedeter ministycznych

Bazując na pojęciach wprowadzonych w REWRITE3, wprowadzone zostały semiautomaty, lewe języki, automaty oraz prawe języki. Zdefiniowane zostały także języki akceptowane przez automaty. Następnie, została przedstawiona determinizacja systemów tranzycyjnych, semiautomatów oraz automatów. Na końcu pokazana jest równoważność automatów deterministycznych i epsilon niedeterministycznych.

Etykietowane systemy tranzycji stanów

Artykuł wprowadza etykietowane systemy tranzycji stanów, gdzie tranzycje mogą być etykietowane słowami z zadanego alfabetu. Korzystając z relacje redukcji z REWRITE1 definiowane są przejścia między stanami, akceptacja słów oraz stany osiągalne. Deterministyczne systemy tranzycyjne także zostały zdefiniowane.

Kwantyfikatory w wyrażeniach regularnych - co najmniej m wystąpień

Jest to drugi artykuł na temat kwantyfikatorów w wyrażeniach regularnych. FLANG_2 wprowadzał kwantyfikatory: od m do n wystąpień oraz wystąpienie opcjonalne. W FLANG_3 zostały wprowadzone następujące kwantyfikatory: co najmniej m wystąpień, domknięcie dodatnie (co najmniej jedno wystąpienie).

Systemy przepisywania słów

Bazując na definicjach z Konstrukcji Kompilatorów, wprowadzone zostały systemy pół-thue'owskie, systemy Thuego oraz relacja bezpośredniej wyprowadzalności. Następnie zdefiniowano standardową relację redukcji oraz, za jej pomocą, wyprowadzenia (korzystając z teorii rozwiniętej w Reduction Relations - REWRITE1). Języki generowane przez systemy przepisywania zdefiniowano jako wszystkie słowa osiągalne z danego słowa początkowego. Na koniec wprowadzono równoważność semisystemów Thuego ze względu na słowo początkowe.

Kwantyfikatory w wyrażeniach regularnych - od m do n wystąpień

Artykuł ten zawiera dowody kilku faktów, które uzupełniają materiał przedstawiony w poprzednim artykule. Następnie, bazując na tej teorii, rozbudowuje narzędzia do dowodzenia faktów na temat języków formalnych w ogólności, a kwantyfikatorów wyrażeń regularnych w szczególności. W tym artykule dwa kwantyfikatory są zdefiniowane a ich właściwości udowodnione: od m do n wystąpień (lub suma przedziału potęg) oraz wystąpienie opcjonalne. Mimo, że wystąpienie opcjonalne jest przypadkiem szczególnym pierwszego operatora (od 0 do 1 wystąpień), często definiowane jest w zastosowaniach wyrażeń regularnych jako oddzielny operator - stąd jego definicja i dowody właściwości w artykule.

Języki formalne - konkatenacja i domknięcie

Języki formalne wprowadzone są jako podzbiory zbioru wszystkich skończonych, indeksowanych od zera, ciągów nad danych zbiorem (alfabetem). Zdefiniowane zostały: konkatenacja, n-ta potęga i domknięcie (Kleene'ego); pokazano właściwości tych pojęć. Na zakończenie, pokazano, że domknięcie alfabetu (rozumianego tutaj jako język słów o długości 1) równa się zbiorowi wszystkich słów nad tym alfabetem oraz, że alfabet jest najmniejszym zbiorem o tej właściwości.

Boole'owskie właściwości zbiorów

Artykuł zawiera definicje zbioru pustego i aksjomaty (w sensie Mizara-MSE) opisujące należenie do zbiorów, zawieranie zbiorów, sumę, iloczyn i różnicę zbiorów. Następnie przeprowadzone są dowody kilkunastu faktów dotyczących wyżej wymienionych relacji i funkcji.

Homomorfizmy i izomorfizmy grup; grupa ilorazowa

Wprowadzone zostały: homomorfizmy i izomorfizmy grup, grupa ilorazowa. Udowodnione zostały także, tak zwane, twierdzenia o izomorfizmach.

Liczby całkowite

W artykule wprowadzone zostały następujące pojęcia: zbiór liczb całkowitych i jego elementy, kongruencje, zaokrąglanie liczb rzeczywistych w dół i w górę, część ułamkowa liczby rzeczywistej, dzielenie całkowite i reszta dzielenia całkowitego. Dodane także następujące schematy: schemat rozdzielania, schemat indukcji całkowitej, schematy minimum i maksimum (istnienie najmniejszej i największej liczby całkowitej spełniającej zadaną własność).

Góra