Jak opisać maszynę Turinga akceptującą język:
\(\displaystyle{ \left\{ ww: w\in \left\{a,b\right\}^{*} \right\}}\)
Maszyna ta nie może zapętlać się. Zasymuluj jej działanie dla słowa: abbabb
[Maszyna Turinga] Maszyna akceptująca język
-
- Użytkownik
- Posty: 2
- Rejestracja: 23 sty 2012, o 14:11
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Pomógł: 2 razy
[Maszyna Turinga] Maszyna akceptująca język
Nieformalnie rozwiązanie wygląda miej więcej tak:
1. Sprawdź parzystość długości i wyznacz środek słowa:
i) Zmień a->A, B->b i przejdź do ostatniego symbolu \(\displaystyle{ \in \left\{ a, b\right\}}\)
ii) Zmień a->A, B->b i jeśli na lewo masz a albo b przejdź do pierwszego symbolu \(\displaystyle{ \in \left\{ a, b\right\}}\)
iii) jeśli na lewo jest a albo b przejdź do i)
Po tym kroku mamy wyraz zapisany dużymi symbolami a głowica maszyny znajduję się nad pierwszym symbolem drugiej połowy słowa WW.
2. Zmień wszystkie A->a i B->b na lewo od środka
i) przejdź w lewo i zmień A->a i B->b aż dojdziesz do początku
Po tym kroku mamy głowicę nad pierwszym symbolem słowa wW, gdzie pierwsza połowa jest zapisana małymi symbolami.
3 porównaj słowo składające się z małych i dużych liter:
i) zmień a->A lub b->B, przejdź w prawo do pierwszego symbolu \(\displaystyle{ \in \left\{ A, B\right\}}\) i sprawdź czy się zgadzają
ii) przejdź do pierwszego symbolu \(\displaystyle{ \in \left\{ a, b\right\}}\) i wykonaj i)
Formalnie należało by zdefiniować całą maszynę Turinga wraz ze zbiorem stanów, funkcji przejść, etc... i udowodnić poprawność.
Pozdrawiam
1. Sprawdź parzystość długości i wyznacz środek słowa:
i) Zmień a->A, B->b i przejdź do ostatniego symbolu \(\displaystyle{ \in \left\{ a, b\right\}}\)
ii) Zmień a->A, B->b i jeśli na lewo masz a albo b przejdź do pierwszego symbolu \(\displaystyle{ \in \left\{ a, b\right\}}\)
iii) jeśli na lewo jest a albo b przejdź do i)
Po tym kroku mamy wyraz zapisany dużymi symbolami a głowica maszyny znajduję się nad pierwszym symbolem drugiej połowy słowa WW.
2. Zmień wszystkie A->a i B->b na lewo od środka
i) przejdź w lewo i zmień A->a i B->b aż dojdziesz do początku
Po tym kroku mamy głowicę nad pierwszym symbolem słowa wW, gdzie pierwsza połowa jest zapisana małymi symbolami.
3 porównaj słowo składające się z małych i dużych liter:
i) zmień a->A lub b->B, przejdź w prawo do pierwszego symbolu \(\displaystyle{ \in \left\{ A, B\right\}}\) i sprawdź czy się zgadzają
ii) przejdź do pierwszego symbolu \(\displaystyle{ \in \left\{ a, b\right\}}\) i wykonaj i)
Formalnie należało by zdefiniować całą maszynę Turinga wraz ze zbiorem stanów, funkcji przejść, etc... i udowodnić poprawność.
Pozdrawiam
-
- Użytkownik
- Posty: 1
- Rejestracja: 9 cze 2014, o 19:35
- Płeć: Mężczyzna
- Lokalizacja: Gdańsk