-
Klasa języków rekurencyjnych akceptowanie
- Klasa języków rekurencyjnych - języki akceptowane przez maszyny Turinga z własnością stopu.
- Uwaga! Nie potrafimy wyróżnić klasy gramatyk, które generują języki rekurencyjne.
-
Domkniętość języków bezkontekstowych ze względu na operacje na językach
-
Domkniętośc języków rekurencyjnie przeliczalnych
-
Domkniętość języków kontekstowych ze względu na operacje na językach
-
Kodowanie Maszyn Turinga
- δ(q,X)=(p,Y,D)
- dla pewnego stanu i pewnego symbolu, głowica wypisuje symbol i przechodzi do stanu p, w kierunku D
- Każda liczba naturalna może reprezentować dokładnie jedną maszynę Turinga=>
- Maszyn Turinga jest przeliczalnie wiele,ale też nieskończenie wiele ( bo zawsze można dodać coś do ciągu i otrzymać nową maszynę)=>
- Języków rekurencyjnie przeliczalnych jest przeliczalnie wiele
-
Domkniętość klasy języków rekurencyjnych
-
język uniwersalny
- Lu- {<m,w>: w∈L(M)}
- język uniwersalny- zbiór takich słów, które składają się z kodu maszyn Turinga oraz słowa akceptowanego przez tą maszynę
Język Lu nie jest językiem rekurencyjnym ale jest rekurencyjnie przeliczalnym
-
Język przekątniowy
- Rozważmy pewną dwuargumentową relację R w iloczynie kartezjańskim zbioru słów nad alfabetem binarnym i zbioru kodów maszyny Turinga. Rozpatrzmy teraz dwustronnie nieograniczoną tabelę, w której kolumny indeksowane są kolejnymi poprawnymi kodami Maszyn Turinga, a wiersze indeksowane są kolejnymi słowami nad alfabetem binarnym w porządku kanonicznym. Wartością elementu r_ij tej tabelki będzie 1, jeżeli maszyna na j-tej kolumnie akceptuje słowo w i-tym wierszu, wpp będzie to 0.
- Językiem przekątniowym nazywamy język tych słów w_i, dla których wartość r_ii jest równa 0.
Ld={w∈{0,1}* : w = wi ∧ wi ∉ L(Mi)}
Ten język nie jest rekurencyjnie przeliczalny.
-
Zawieranie się języków regularnych w bezkontekstowych
-
Zawieranie się języków bezkontekstowych w kontekstowych
-
Zawieranie się języków rekurencyjnie przeliczalnych w wszystkich
-
Zawieranie się języków rekurencyjnych w językach rekurencyjnie przeliczalnych
-
Zawieranie się języków kontekstowych w językach rekurencyjnych
Każdy język kontekstowy jest językiem rekurencyjnym.
-
Podstawienie
Dane są alfabety ∑ i ∆. Podstawieniem na automacie ∑ nazywamy funkcję f: ∑ -> 2^(∆*), która znakom z ∑ przypisuje języki nad ∆.
- Uogólnienie 1:
- f': ∑* -> 2^(∆*)
- f'(ε) = {ε}
- f'(wa) = f'(w) ° f(a), w ∈ ∑*, a ∈ ∑
- Uogólnienie 2:
- f'': 2^(∑*) -> 2^(∆*)
- f''(L) = ∪(w∈L) f'(w)
-
Homomorfizm
- Podstawienie h które każdej literze alfabetu ∑ przyporządkowuje język nad alfabetem ∆ zawierający dokładnie jedno słowo
- ∀a∈∑ |h(a)|=1
-
Ilorazy języków
Dane są języki L₁ i L₂. Ilorazem lewostronnym tych języków nazywamy:
L₁ \ L₂ = {y: ∃x ∈ L₂ xy ∈ L₁}
prawostronny:
L₁ / L₂ = {x: ∃y ∈ L₂ xy ∈ L₁}
-
Ruch maszyny Turinga
Ruch maszyny Turinga opiszemy w postaci pary opisów chwilowych określających konfigurację maszyny przed wykonaniem ruchu i konfigurację po wykonaniu ruchu.
Ruch MT interpretowany jest jako pewna relacja binarna nad zbiorem opisów chwilowych, gdzie |- jest symbolem tej relacji, a relację będziemy nazywać relacją ruchu.
|
|