WR - AS , JBK - AZS , JRP - MT

1. AS.

To piątka uporządkowana M=(Q, Σ, δ, q₀, F),

Q - skończony zbiór stanów,

Σ - skończony alfabet wejściowy,

δ - f-cja przejścia, która jest odwzorowaniem: DAS: δ: Q×Σ → Q,

NAS: δ: Q×∑ → 2_­^Q;

q₀∈Q - stan początkowy,

F⊆Q - zbiór stanów końc., stanowiących „sukces”

2. Język akceptowany przez AS.

Łańcuch x jest akceptowany przez AS M=(Q, Σ, δ, q₀, F)

jeśli δ(q₀,x)=p i p∈F. Język akceptow. przez M oznaczamy:

L(M)={x: δ(q₀,x)∈F}. Język nazywamy zbiorem regularnym

jeśli jest on językiem akceptowanym przez jakiś AS.

3. Dwa p i q AS są odróżnialne.

Dwa stany p i q są odróżnialne, jeśli:

4. WR i własności.

Wyrażenia regularne nad Σ definiujemy rekursywnie:

1)∅, ε są WR; 3) dla każdego a∈Σ jest WR, {a}; 4) jeśli r i s

są WR, reprezentującymi języki R i S, to: r+s, rs, r* są

wyrażeniami reprez. zbiory R u S, RS, R*.

* ma wyższy prior. niż złożenie, a złożenie niż dodawanie.

e+e=e; e₁+e₂=e₂+e₁; εe=eε=e; (e₁+e₂)+e₃=e₁+(e₂+e₃);

(e₁e₂)e₃=e₁(e₂e₃); (e₁+e₂)X=e₁X+e₂X; e*e=ee*; (e*)*=e*

5. Tw. dotyczące WR.

1. Niech r będzie WR. Wtedy istnieje NAS z ε-przejściami,

który akceptuje L(r). 2. Jeżeli L jest akceptow. przez DAS,

to L jest reprezentowany przez wyrażenie regularne.

L², (r+s)*, (10+11)*, L₁, L₂, L⁺, L^x

L²=LL¹ bo Lⁱ=LL^i-1 dla i ≥1 - WR należące do Σ*-zbiorów napisów, które można utworzyć z alfabetu Σ);

(r+s)* domknięcie sumy języków r i s (r i s są WR, reprez. odpowiednio jęz. R i S, (r+s) reprez. RuS; R*- domknięcie.

(10+11)*={ε, 10, 11, 1010, 1011, 1111…} -zb. Wszystkich łańcuchów stworzonych z 10 i 11;

L₁ i L₂ są to zbiory łańcuchów z Σ*;

L⁺=U^∞_i=1Lⁱ - domknięcie dodatnie zbioru L (zb. wszystkich słów otrzymanych ze złożenia dowolnej liczby słów za

wyjątkiem złożenia zera słów (ε);

L^x - suma teoriomnogościowa.

L₁L₂={xy: x∈L₁, y∈L₂} ; L⁰={ε} ; L^*=U^∞_i=0Lⁱ,

6. JR.

JR (ang. regular language) to język formalny taki, że istn.

automat o skończ. liczbie stanów potrafiący zdecydować,

czy dane słowo należy do języka.

7. DAS o min. liczbie stanów.

DAS konstru. ze wszystkich par stanów odróżnialnych

z usuniętymi stanami nieosiągalnymi. Wtedy jest AS o

minimalnej liczbie stanów dla swojego języka L.

8. Automat Moore'a.

To szóstka uporządkowana M=(Q,Σ,Δ,δ,λ,q₀), gdzie

Q,Σ,δ,q₀ są określone jak w DAS.

Δ - alfabet wyjściowy,

λ - funkcja wyjścia (odwzorowanie) λ: Q → Δ

DAS jest szczególnym przyp. automatu Moore'a ∆={0,1}.

9. Automat Mealy'ego.

To szóstka uporządkowana M=(Q,Σ,Δ,δ,λ,q₀) gdzie

Q,Σ,δ,q₀ są określone jak w DAS.

Δ - alfabet wyjściowy,

λ - funkcja wyjścia (odwzorowanie) λ: Q×∑ → Δ

10. Automat ze stosem.

AZS to siódemka uporządkowana M=(Q, Σ,δ,Γ,q₀,z­­₀,F)

Q,Σ,δ,q₀,F są określone jak w DAS.

Γ - skończony alfabet stosowy,

z­­₀ ∈F - symbol początkowy stosu,

δ - funkcja przejścia (odwzorowuje δ: Qx(Σu{Ɛ})xΓ→2^2xF*

(Ɛ-symbol wyjścia, Γ-symbol na stosie)

11. Związek: automat ze stosem i język bezkontekst.

TW: Jeśli L jest JBK, to istn. Niedeterm. AZS M, taki że

L=N(M), gdzie N(M) jest językiem akceptow. przez M. Jeżeli L jest językiem akceptowanym przez AZS przy

pustym stosie, to L jest JBK.

12. Gramatyka bezkontekstowa. Własności JBK.

GBK zapisujemy w postaci G=(V,T,P,S) gdzie

V - skończony zb. zmiennych końcowych,

T - skończony zb. symboli końcowych. Zał.: VnT=ø

P - skończony zb. produkcji [prod. ma postać A→α,

A - zmienna; α - łańcuch symboli z (VuT)*], S - specjalna zmienna, zwana symbolem początkowym.

JRP są zamknięte ze względu na:

-sumy teoriomnogościowe, złożenia i domkn.Kleene'go,

- podstawienie,

- homomorfizmy i przeciwobrazy homomorficzne.

NIE są z. ze wzgl. na iloczyn teoriomnogościowy i dopełn.

13. Język rekurencyjnie przeliczalny. Własności JRP.

JRP to język formalny określany jako język klasy 0 w hier. Chomsky'ego, jest on językiem akceptowany przez MT. Jest to rekurencyjnie przeliczalny podzbiór zbioru wszystkich słów nad danym alfabetem.

JRP są zamknięte ze wzgl. na:

- domknięcie Kleen'ego z L - L* ,

- konkatencję języków L i P - L o P,

- sumę L u P,

- przecięcie L n P.

14. Maszyna Turinga.

Alan Turing. Formalnie MT to M=(Q,Σ,Γ,δ,q₀,B,F)

Q - skończony zbiór stanów;

Γ- skończony zb. dopuszczalnych symboli taśmowych;

B ∈Γ- symbol pusty;

Σ - podzbiór zb. Γ, niezawieraj. B (zb. symboli wejścio.);

q₀∈Q - stan początkowy,

F⊆Q - zbiór stanów końcowych,

δ - funkcja przejścia (odwzorowanie δ: QxΓ →QxΓx{L,P}

[L - ruch w lewo, P - w prawo]).

Zależnie od symbolu obserw. przez głowicę MT w pojedyn. ruchu może: 1) zmienić stan, 2) drukować symbol w bieżącej komórce, nadpisując poprz. 3) przesunąć głowicę o jedną komórkę w prawo lub w l.

15. Różnica miedzy MT a 2-DAS.

Różnica pomiędzy MT a 2-kierunk. DAS polega na tym, że MT może zmienić stan, z którego wychodzi.

16. Złożoność czasowa.

Niech M oznacza MT z k taśmami dwustron. nieskończ.

Wejście jest na jednej z taśm. Na wszystkich taśmach dozwolone jest zapisywanie symboli.

Def.: Jeśli dla każdego słowa wejściowego o dł. n maszyna M wykona C(n) ruchów, to mówimy, że M jest MT z ogranicz. czasowym C(n) lub o złożoności czas. C(n).

17. Tw. o hierarchii czasowej.

Jeśli C₂(n) jest funkcją w pełni konstruowalną czasowo oraz lim_n→∞[C₂(n)^.logC₁(n)]/C₂(n) =0, to istn. język L∈DCZAS(C₂(n)) i L∉DCZAS(C₁(n)).

18. Tw. o hierarchii pamięciowej.

Jeśli P₂(n) jest funkcją konstruowalną pamięciowo oraz P₁(n)>log₂n, P₂(n)≥log₂n, lim_n→∞P₁(n)/P₂(n) =0, to istn. język L∈DPAM(P₂(n)) i L∉DPAM(P₁(n)).

19. Problem klasy P i NP.

Problem P (-deterministycznie wielomianowy) to probl.

decyzyjny, dla którego rozwiąż. można znaleźć w czasie wielomianowym. P=U_i≥1DCZAS(nⁱ), nⁱ-złożoność wielom.

Problem NP (niedeterministycznie wielomianowy) to probl. decyzyjny, dla którego rozwiąż. można zweryfik.

w czasie wielomianowym. NP=U_i≥1NCZAS(nⁱ)

Jednym z najważniejszych problemów inform. jest: czy P=NP? Wiadomo, że P⊆NP, nie wiadomo natomiast, czy istnieje problem NP, który nie jest w klasie P.

20. DPAM(P(n)) i NPAM(P(n)); DCZAS(C(n)) i N-… .

DPAM(P(n)) - rodzina języków o determin. złożoności pamięciowej P(n), NPAM(P(n)) - o niedeterministycznej.

1. Tw. Savitcha: Jeżeli L∈NPAM(P(n)), to L∈DPAM(P²(n)), więc NPAM(P(n))⊆DPAM(P²(n)).

2. Jeżeli L∈NCZAS(f(n)), to ∀_c>1 L∈DCZAS(c^f(n)).

Problem klasy DPAM(P(n)) może być rozwiązany na DMT z użyciem O(P(n)) pamięci, NPAM na NMT z użyciem

O(P(n)) pamięci.

Lemat o pompowaniu

Niech L będzie zbiorem regularnym, wtedy istnieje stała n taka, że jeśli z jest dowolnym słowem z L
oraz , to z możemy przedstawić w postaci:

gdzie

1 oraz

n - liczba stanów najmniejszego automatu skończonego (AS) akceptującego L.

---