Maszyna TURINGA - Pomoc online
- Warszawa, mazowieckie
- 24 Cze 16:31
- Nr ogłoszenia: 60486388
1 / 1
Obserwuj
- Oferta od osoby prywatnej
Skonstruuję maszynę Turinga lub napiszę program symulujący pracę maszyny Turinga w takich językach jak C, C++, C#, Python, Java, Matlab itp. Cena do uzgodnienia.
Przykłady maszyn i programów
1. Skonstruuj maszynę Turinga (może być jednotaśmowa lub wielotaśmowa), która akceptować będzie zbiór słów postaci {n ∗ m ∗ k | n, m, k ∈ N, n + m = k}. Innymi słowy, maszyna ma akceptować słowa, które składają się z trzech ciągów symboli oddzielonych symbolem ‚∗’, spośród których każdy ciąg reprezentuje liczbę naturalną, a liczba reprezentowana przez trzeci z nich jest sumą liczb reprezentowanych przez dwa poprzednie. Alfabet maszyny możemy zdefiniować jako: Σ = {∗, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, albo jako Σ = {∗, 0, 1} w pierwszym przypadku liczby będą przedstawione w zapisie dziesiętnym (a więc takim, jakim posługujemy się na co dzień), w drugim – w zapisie
dwójkowym. Na przykład, jeśli zdecydujemy się na zapis dziesiętny, słowo postaci 10 ∗ 21 ∗ 31 zostanie przez maszynę zaakceptowane, ale słowa 0 ∗ 5 ∗ 6 lub ∗00 ∗ 5∗ – już nie. Dla zapisu dwójkowego słowo 10 ∗ 11 ∗ 101 zostanie zaakceptowane, zaś słowa 10 ∗ 10 ∗ 10 czy ∗1 ∗ ∗001 – już nie.
2. Skonstruować Deterministyczną Maszynę Turinga (DMT) akceptującą język NAWIASY. Ciąg znaków [[][]][] należy do tego języka, natomiast ciąg znaków ]][ nie należy do języka NAWIASY.
3. Skonstruuj Maszynę Turinga, która zamienia liczbę w systemie trójkowym na liczbę w systemie siódemkowym lub skonstruuj Maszynę Turinga, która konwertuję liczbę z systemu siódemkowego na system trójkowy.
4. Skonstruować Maszynę Turinga, która podwaja każdy bit wejściowej liczby binarnej. Na przykład z liczby 101 powinniśmy otrzymać 110011.
5. Twoim zadaniem jest opracowanie maszyny Turinga, która posortuje bity dowolnej liczby binarnej ustawiając wszystkie 0 po prawej stronie, a 1 po lewej. Na przykład liczba 10111001 musi zostać przekształcona do postaci 11111000.
6. Niech Σ = {0, 1} (a zatem alfabet maszyny składa się tylko z dwóch elementów:
0 i 1). Skonstruuj maszynę Turinga (może być deterministyczna lub niedeterministyczna), która będzie akceptować zbiór słów postaci { AA | A ⊆ Σ ∗ }. Innymi słowy, maszyna akceptować będzie jedynie takie słowa, które składać się będą z dwóch identycznych, występujących po sobie kopii jakiegoś ciągu zer i jedynek. Na przykład słowo 00100010 byłoby zaakceptowane przez taką maszynę (jako składające się z dwóch występujących po sobie kopii ciągu 0010), ale już ciąg 01001 – nie.
7. Zadanie ze Wstępu do Informatyki. Należy utworzyć maszynę Turinga, która zamieni liczbę umieszczoną na taśmie zapisaną w systemie dwójkowym na liczbę zapisaną w systemie dziesiętnym, oraz odwrotnie, maszynę która zamieni liczbę zapisaną w systemie dziesiętnym na liczbę zapisaną w systemie dwójkowym.
8. Wykorzystując maszynę Turinga napisz program, który będzie symulował zwiększanie liczby zapisanej w systemie binarnym o 3. Wymagania ogólne:
• Program musi wykorzystywać algorytm maszyny Turinga, to znaczy muszą istnieć zdefiniowane stany i przejścia między nimi.
• Oprócz programu należy dołączyć schemat blokowy przedstawiający działanie maszyny Turinga oraz tablicę przejść.
• Program musi umożliwiać wprowadzanie przez użytkownika liczby, która ma zostać zwiększona o 3.
• Po zakończeniu działania programu należy wyświetlić po kolei wszystkie stany, przez które program przeszedł.
• Program w wersji konsolowej.
• W konsoli po każdym wykonanym kroku ma być wyświetlony aktualny stan taśmy i zaznaczona pozycja głowicy.
• W konsoli przy każdym wykonanym kroku ma być wyświetlony stan, w którym aktualnie znajduje się maszyna Turinga.
9. Zadaniem jest napisanie programu symulującego działanie deterministycznej maszyny Turinga zdefiniowanej na wykładzie (dokładnie takiej, istnieje wiele definicji maszyn Turinga różniących się szczegółami). Oczywiście taśma musi być skończona. Początkowo długość taśmy powinna wynosić 32 komórki. Każdorazowo, gdy głowica osiągnie kraniec taśmy, to należy dokonać rozszerzenia taśmy, z odpowiedniej strony, o kolejne 32 komórki. Dobrze byłoby, aby na ekranie pojawiał się komunikat, gdy następuje rozszerzenie taśmy.
Program powinien dać możliwość oglądania wyników działania kolejnych kroków działania maszyny, czyli jej kolejnych konfiguracji. Sposób zobrazowania konfiguracji pozostawiam Państwu do wyboru, byle był czytelny. Do wypisywania konfiguracji można użyć standardowego wyjścia (ekranu) lub pliku. Powinna też być dostępna opcja wykonania obliczeń maszyny bez wypisywania kolejnych konfiguracji tak, by dało się obejrzeć wyniki w przypadku długich obliczeń.
Przed zakończeniem swego działania program powinien wyraźnie wypisać, co jest wynikiem obliczeń (słowo obliczone) i jakie było słowo początkowe. W przypadku, gdy maszyna Turinga wpada w obliczenia nieskończone, program również powinien się nie kończyć (można po np. 1000 konfiguracjach przestać je wypisywać, ale program powinien liczyć dalej). W przypadku obliczenia zakończonego błędem powinien pojawić się stosowny komunikat. Oprócz obliczonego słowa należy wypisać długość obliczenia.
Skontaktuj się
zadania24h - Mateusz Magiera
Liczba odsłon: 2957
Zgłoś nadużycie
