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ć?
[Teoria złożoności] Złożoność dla maszyny Turinga
[Teoria złożoności] Złożoność dla maszyny Turinga
Ostatnio zmieniony 30 kwie 2013, o 15:44 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
- 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
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}\).