Машината на Тюринг като универсален разпознавач - Студопедия
Както е известно, с помощта на MT може да се дефинира много широк клас езици, наречени рекурсивно изброими.
Дефиниция. Рекурсивно изброим език е формален език, за който има машина на Тюринг (или друга изчислима функция), която ще спре и ще вземе всеки входен низ от този език.
Всички обикновени, контекстно-свободни, контекстно-чувствителни и рекурсивни езици са рекурсивно изброими.
Ако добавим неограничена външна памет към модела KA, тогава получаваме автомат, който изпълнява всеки алгоритъм. Такъв автомат се наричамашина на Тюринг(MT).
MT се състои от 2 части: лента и държавна машина. Обикновено при моделите МТ лентата е неподвижна, а главата се движи спрямо лентата под управлението на машината (ляво, дясно, стои неподвижно).
MT може да изпълнява следните команди:
1) напишете нов символ в клетката на лентата;
2) преместете една клетка наляво или надясно;
3) преминете към ново вътрешно състояние.
MT не може да направи нищо друго.
MT е дадено: T = (Q, S, Γ, δ, q0, F),
1) набор от вътрешни състояния Q=1…qm>;
2) начално състояние q0
3) набор от крайни състояния F
5) азбуката на валидните знаци на лента G
6) команди за движение на главата.
7) управляваща програма δ, която може да бъде зададена както в текстова, така и в таблична форма:
Ще приемем, че МТ, разпознаващ езика L, спира, т.е. няма следващ ход, когато се получи входен низ.
Пример. Задайте език L = .
Задаваме МT = (Q, S, Γ, δ, q0, F),
Главата е на първия знак от веригата.
MT програма δдефинирайте както следва:
1. δ(q0, 0) = (q1, X, R).
В състояние q0 символът 0 се заменя с X и машината се премества надясно в състояние q1, търсейки 1.
2. а) δ(q1, 0) = (q1, 0, R);
b) δ(q1, Y) = (q1, Y, R);
в) δ(q1, 1) = (q2, Y, L).
Оставайки в състояние q1, колата се движи надясно през всички нули (секция 2a) и блок Y (секция 2b). След като се натъкне на 1, той го заменя с Y и преминава в състояние q2, започвайки да се движи наляво (стр. 2c).
3. а) δ(q2, Y) = (q2, Y, L);
b) δ(q2, X) = (q3, X, R);
в) δ(q2, 0) = (q4, 0, L).
Оставайки в състояние q2, автомобилът се движи наляво през блок Y (секция 3a). Ако колата срещне X, докато все още е в състояние q2, тогава няма повече 0 за замяна с X и колата преминава в състояние q3, започвайки да се движи надясно, за да се увери, че няма останали 1 (Раздел 3b). Ако се срещне 0, колата преминава в състояние q4, за да продължи да се движи в търсене на най-лявата 0 (секция 3c).
4. а) δ(q4, 0) = (q4, 0, L)
б) δ(q4, X) = (q0, X, R).
Колата се движи през нулите (секция 4а). Ако се срещне X, тогава машината е преминала най-лявата нула. Тя трябва, като се движи надясно, да превърне тази 0 в X (секция 4b). Има преход към състояние q0 и процесът, току-що описан в раздели 1–4, продължава.
5. а) δ(q3, Y) = (q3, Y, R)
b) δ(q3, B) = (q5, Y, R).
Машината влиза в състояние q3, когато не остане нито една 0 (виж раздел 3b). Колата трябва да се движи надясно (стъпка 5a) през блок Y. Ако има празнина преди 1, тогава не остава 1 (стъпка 5b). В тази ситуация машината преминава в крайно състояние q5 и спира, като по този начин сигнализира за приемането на входния низ.
6. Във всички случаи, с изключение на 1–5, функцията δ не е дефинирана. MTще спре и ще отхвърли въведения низ.
Табличен запис на функцията δ.
| х | Y | IN | |||
| q0 | q1, X, R | респ. | респ. | респ. | респ. |
| q1 | q1, 0, R | q2, Y, L | респ. | q1, Y, R | респ. |
| q2 | q4, 0, L | респ. | q3, X, R | q2, Y, L | респ. |
| q3 | респ. | респ. | респ. | q3, Y, R | q5, Y, R |
| q4 | q4, 0, L | респ. | q0, X, R | респ. | респ. |
Помислете за действията на машината на Тюринг върху входния низ 000111.
Таблицата показва конфигурациите на символния низ на лентата с маркера за състояние под сканирания знак (в конфигурации 25 и 26 маркерът за състояние е под знака за интервал).
В някои задачи MT може да се използва катоустройство с памет за съхраняване на ограничено количество информация. А именно: състоянието се записва като двойка елементи, като единият контролира, а другият съхранява символа.
Пример. Посочете език, състоящ се от низове, в които първият знак не се среща многократно в един и същи низ.
Нека построим функцията δ (програма MT), както следва:
1. а) δ([q0, B], 0) = ([q1, 0], 0, R);
b) δ([q0, B], 1) = ([q1, 1], 1, R).
Устройството съхранява сканирания знак във втория компонент за обозначаване на състоянието и се измества надясно. Първият компонент става q1.
2. а) δ([q1, 0], 1) = ([q1, 0], 1, R);
b) δ([q1, 1], 0) = ([q1, 1], 0, R).
Ако една машина запомни 0 и види 1, или обратното, запомни 1 и види 0, тогава тяпродължава да се движи надясно.
3. а) δ([q1, 0], B) = ([q1, B], 0, L);
b) δ([q1, 1], B) = ([q1, B], 0, L).
Машината влиза в крайното състояние [q1, B], ако срещне знак за интервал, преди да достигне второто копие на най-левия знак. Ако машината достигне празнина в състояние [q1, 0] или [q1, 1], тогава тя приема входния низ. За състоянието [q1, 0] и символ 0, или за състоянието [q1, 1] и символ 1, функцията δ не е дефинирана, така че ако машината някога види запаметения знак, тя спира, без да приеме.
Табличен запис на функцията δ.
| IN | |||
| [q0,B] | [q1, 0], 0, R | [q1, 1], 1, R | [q0,B], B, R |
| [q1,0] | респ. | [q1, 0], 1, R | допуснати |
| [q1,1] | [q1, 1], 0, R | респ. | допуснати |
В общия случай може да бъде разрешен произволен фиксиран брой компоненти, като всички освен един са предназначени за съхраняване на информация.
Не намерихте това, което търсихте? Използвайте търсачката:
Деактивирайте adBlock! и обновете страницата (F5)наистина е необходимо