1.2. Relacje Określenie relacji: Relacja R jest zbiorem par uporządkowanych, czyli podzbiorem iloczynu kartezjańskiego dwóch zbiorów: A (dziedzina relacji) i B (przeciw...
3. Gramatyki bezkontekstowe 3.1. Rozbiór gramatyczny Niech będzie dana gramatyka bezkontekstowa G = . Gramatyki rekursywne Gramatykę nazywamy rekursywną, jeżeli w gramatyce tej możliwe jest wyprowadzenie A ⇒+ αAβ dla pewnego ...
5. Maszyna Turinga A = ∈ AT Q — skończony zbiór stanów q0 – stan początkowy F – zbiór stanów końcowych Γ– skończony zbiór symboli taśmy T ⊆ Γ — alfabet wejściowy b ∈ T–Γ — symbol pusty (blank) δ: Q×Γ ! 2Q×Γ×{L,R} — funkcja przejśc...
1. Pojęcia podstawowe, oznaczenia 1.1. Zbiory Pojęcia pierwotne: ─ zbiór ─ element zbioru ─ przynależność elementu x do zbioru A x∈A Konstruktor zbioru: { x | P(x) } oznacza „zbiór elementów x, takich że P(x) jest prawdziwe”, gdzie P(x) jest pewnym stwierdzeniem (predykatem) o elementach x...
4. Zbiory regularne, automaty skończone 4.1. Zbiory regularne, wyrażenia regularne Zbiory regularne Niech T będzie alfabetem. Zbiór regularny nad alfabetem T definiujemy następująco: (1) ∅ – zbiór pusty jest zbiorem regularnym, (2) {ε} –...
4.5 Deterministyczne i zupełne automaty Moore’a i Mealy’ego Automaty Moore’a i Mealy’ego będziemy rozważać tylko w wersji deterministycznej i zupełnej. W definicjach tych automatów nie pojawia się pojęcie stanów końcowych, za to mamy taśmę wyjściową, na którą automat zapisuje symbole z alfabetu...
