Информатика Машина Тьюринга

Question

Информатика Машина Тьюринга

Тимур Забабурин Ученик (107), на голосовании 2 дня назад

Как сделать в эмуляторе машины Тьюринга такую задачу, есть алфавит a, b, c. заменить в слове p все пары ab на c

Answer 1

 (q0, a) → (q1, c, R) 
(q0, b) → (q0, b, R) 
(q0, c) → (q0, c, R) 
(q0, _) → (q_accept, _, S) 
(q1, b) → (q0, _, R) 
(q1, a) → (q0, a, R) 
(q1, c) → (q0, c, R) 
(q1, _) → (q_accept, _, S)

Answer 2

в общем, так как-то:

0,* -> 0,*,R
0,a -> 1,a,R
0,b -> 0,b,R
0,c -> 0,c,R
0,_ -> 2,_,L

1,a -> 1,a,R
1,b -> 1,b,R
1,c -> 1,c,R
1,_ -> 3,_,L

2,c -> 2,c,L
2,b -> 2,c,L
2,* -> 5,*,S

3,* -> 4,*,R
3,a -> 3,_,L
3,b -> 3,_,L
3,c -> 3,_,L

4,_ -> 5,a,L

здесь:
{0,1,2,3,4,5} - состояния,
0 - начальное состояние,
5 - конечное состояние,
* - маркёр начала ленты
_ - пустой символ