[Teoria złożoności] Złożoność dla maszyny Turinga

adver89
Użytkownik
Użytkownik
Posty: 11
Rejestracja: 17 lut 2009, o 11:57
Płeć: Mężczyzna

[Teoria złożoności] Złożoność dla maszyny Turinga

Post autor: adver89 »

Witam
Jaka jest czasowa złożoność obliczeniowa maszyny Turinga (det.) dla języków:
\(\displaystyle{ a) L=\left\{a^{n}bc^{m}|n,m \le 1 \right\}}\)
\(\displaystyle{ b) L=\left\{a^{n}bc^{n}|n \le 1 \right\}}\)
i jak to uzasadnić?
Ostatnio zmieniony 30 kwie 2013, o 15:44 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
bartek118
Użytkownik
Użytkownik
Posty: 5974
Rejestracja: 28 lut 2010, o 19:45
Płeć: Mężczyzna
Lokalizacja: Toruń
Podziękował: 15 razy
Pomógł: 1251 razy

[Teoria złożoności] Złożoność dla maszyny Turinga

Post autor: bartek118 »

Pierwszy przykład jest bardzo prosty - wystarczy przeczytać słowo od początku do końca, więc złożoność to \(\displaystyle{ n+m+1}\).
ODPOWIEDZ