Теория конечных языков и автоматов. Курс лекций П. Н. Иваньшин 2
 Скачать 0.61 Mb.
|
|
, . . . , ? m p , кото- рые вместе с состояниями и вводом определяют используемые правила. По применению всех возможных последовательностей, мы получим все возможные вычисления. То есть, если слово воспринимается машиной Тьюринга T , оно также воспринимается одной из приведенных последо- вательностей. Задачи 1. Построить (не обязательно детерминированные) машины Тьюринга, соответствующие языкам a) Язык из строк, содержащих вдвое больше a чем b. b) Язык из строк, содержащих одно и то же количество a и b. c) Язык {a n b n |n = 1, 2, . . .} d) Язык {a n b k c n |k, n = 1, 2, . . .} e) Язык из палиндромов нечетной длины над алфавитом {a, b, c}. f) Язык из палиндромов четной длины над алфавитом {a, b, c}. g) Язык из палиндромов над алфавитом {a, b, c}. h) Язык {a n b n a m b m |m, n = 1, 2, . . .} i) Язык {a n b 2n a m b 2m |m, n = 1, 2, . . .} 54 Глава 4. Машина Тьюринга 4.3 Проблема остановки для машин Тьюрин- га Проблема остановки Существует ли алгоритм, определяющий, для данной машины Тьюринга T и произвольной строки w, достигнет ли T конечного состояния после обработки w? Определение 42. Язык L разрешим по Тьюрингу, если существует машина Тьюринга, которая по приведенному слову выдает Y если слово принадлежит L и N в противном случае. Теорема 32. Если язык разрешим по Тьюрингу, то он принимается некоторой машиной Тьюринга. Доказательство. Если язык разрешим по Тьюрингу, то существует ма- шина Тьюринга, которая по приведенному слову выдает Y если слово принадлежит L и N в противном случае. Модифицируем эту машину так, чтобы вместо печати N, она зацикливалась, а вместо вывода Y , останавливалась. Теорема 33. Если язык L разрешим по Тьюрингу, то и язык L 0 = A ? \L разрешим по Тьюрингу. Доказательство. Если язык L разрешим по Тьюрингу, то существует машина Тьюринга, которая по приведенному слову выдает Y если слово принадлежит L и N в противном случае. Модифицируем эту машину так, чтобы вместо печати N, она выдавала Y и наоборот. Теорема 34. Язык L разрешим по Тьюрингу ? оба языка L и L 0 при- нимаемы по Тьюрингу. Доказательство. (?) Если язык L разрешим по Тьюрингу, то по теоре- ме 33 его дополнение L 0 тоже разрешимо по Тьюрингу. Следовательно, по теореме 32 оба языка L и L 0 принимаемы по Тьюрингу. (?) Пусть существую машины Тьюринга M и M 0 , принимающие L и L 0 , соответственно. Если строка ввода принимаема M, введем Y . Ес- ли она принимается M 0 , выведем N. Так как этот процесс алгоритмичен, по гипотезе Черча его можно реализовать в виде машины Тьюринга M 00 Следовательно L разрешим по Тьюрингу и по теореме 33, L 0 тоже раз- решим по Тьюрингу. Теорема 35. Любая машина Тьюринга над алфавитом {a, b} однозначно реализуется в виде строки из a и b. 4.3. Проблема остановки для машин Тьюринга 55 Доказательство. Пусть множество состояний машины S = {s 1 , s 2 , s 3 , . . . , s n } Каждое правило имеет вид (s i , a 1 , s j , a 2 , N ), где a 1 , a 2 ? {a, b} S{], O}, N ? {L, R, ]}. Заменим s i на строку из i букв a. После этой строки пишем b разделитель. Заменим символы a, b, ], O на aa, bb, ab, ba, соответственно. Последний символ L заменяем на a, а R на b. Например, строка для (s 4 , b, s 2 , ], R) aaaabbbaababb, где aaaa представляет s 4 , b разделитель, bb b, aa s 2 , b разделитель, ab ], b R. Обозначим строку, представляющую машину Тьюринга M, через c(M). Теорема 36. Существует язык, принимаемый некоторой машиной Тью- ринга, но не разрешимый по Тьюрингу. Доказательство. Рассмотрим язык L 0 , состоящий из строк c(M)bw, пред- ставляющих машину Тьюринга M и строк w, принимаемых M. Легко по- строить машину Тьюринга IMM, принимающую L 0 . Для данной строки t , MM сначала расшифровывает t и если строка представляет строку машину Тьюринга M и вводную строку, MM поставляет последнюю подстроку t в M, и MM принимает t = c(M)bw ? M принимает w. Следовательно, L 0 принимаем по Тьюрингу. Если, кроме того, L 0 разрешим по Тьюрингу, то каждый принимае- мый по Тьюрингу язык разрешим по Тьюрингу. Докажем, что L 0 не разрешим по Тьюрингу. Докажем сначала, что ес- ли L 0 разрешим по Тьюрингу, то и язык L 1 = {c(M )|M принимаетc(M)} тоже разрешим по Тьюрингу. Построим M 1 по следующим правилам: Для строки s, рассмотрим строку sbs и используем ее как ввод для MM 2 (машина, принимающая L 0 ). Если MM 2 выводит Y , то s = c(M) для некоторой машины M, принимающей c(M). Следовательно, s ? L 1 и M 1 тоже выводит Y . Если MM 2 выдает N, то s = c(M) для каждой ма- шины M, которая принимает c(M), то есть s 6? L 1 и M 1 выводит N. Следовательно. L 1 разрешим по Тьюрингу. Покажем, что L 1 не разрешим по Тьюрингу. По теореме 33 L 1 раз- решим по Тьюрингу ? L 0 1 разрешим. То есть, достаточно доказать, что L 1 не разрешим по Тьюрингу. Язык L 1 = {{w|w ? {a, b} ? } либо w = c(M ) для каждой машины M, либо w = c(M) для некоторой машины M, но M не принимает w}. Вспомним парадокс Расселла. Пусть M 0 1 машина, принимающая L 0 1 , тогда верно ли, что c(M 0 1 ) ? L 1 ? Если так, то M 0 1 не 56 Глава 4. Машина Тьюринга принимает c(M 0 1 ) по определению L 0 1 . Но M 0 1 принимает c(M 0 1 ) поскольку она принимает любой элемент L 0 1 , и мы пришли к противоречию. Пред- положим теперь, что c(M 0 1 ) 6? L 0 1 . Тогда c(M 0 1 ) ? L 1 . Следовательно, M 0 1 принимает c(M 0 1 ) по определению L 1 . Но M 0 1 принимает только элементы L 0 1 , то есть c(M 0 1 ) ? L 0 1 , снова противоречие. Задачи 1. Доказать, что конечное множество всегда разрешимо по Тьюрингу. 2. Построить строку, соответствующую правилу (s 5 , O, s 2 , a, R) 3. Найти c(M), где M машина, определяемая правилами (s 1 , a, s 2 , a, R), (s 1 , b, s 2 , b, R), (s 2 , a, s 2 , a, R), (s 2 , b, s 2 , b, R), (s 1 , ], s 3 , ], R). 4. Найти c(M), где M машина, определяемая правилами (s 1 , a, s 2 , ], R), (s 1 , b, s 2 , a, R), (s 2 , a, s 2 , ], R), (s 2 , b, s 2 , a, R), (s 1 , ], s 3 , ], R). 5. Найти правило, соответствующее строке a) aaabababbaa. b) aabbbaaabbab. 6. Которые из строк представляют правила? a) baaabbaabb; b) aabbbaaabbbb; c) aababaabbaa; d) aabaabaabaab; e) aabaaabbabb. 7. Восстановить машину Тьюринга по строке a) abaaabbbbaabbbabaabababbaababb; b) abaaaababbabbbaababbaababaaababb. 8. Восстановить машину Тьюринга и строку ввода по строке a) abaaaabbbbabbbaabbbbaabbbabbbaababaaababbbaaabbb; b) abaaaabbbbabbbaabaabaabbbabbbaaabaaabbbaaababaaababababaabb. 9. Построить метод кодирования, который допускает использование символов A и B наравне с a, b посредством применения слов длины 3 для обозначения вводимых символов. 10. Используйте код из предыдущей задачи для нахождения строки, представляющей (s 1 , a, s 3 , A, R). 4.4. Проблемы неразрешимости для контекстно-свободных языков 57 11. Найти строку, реализующую машину (s 1 , a, s 2 , b, R), (s 1 , b, s 2 , b, R), (s 2 , a, s 2 , ], R), (s 2 , b, s 2 , b, R), (s 1 , ], s 3 , ], R) вместе с вводимым словом ababaab. 12. Найти строку, реализующую машину (s 1 , a, s 2 , b, R), (s 1 , b, s 2 , a, R), (s 2 , a, s 2 , ], R), (s 2 , b, s 2 , ], R), (s 1 , ], s 3 , ], R) вместе с вводимым словом babbab. 13. Пусть L язык. Доказать, что верно только одно из перечислен- ного: a) Ни L ни L 0 не принимаются машинами Тьюринга. b) И L и L 0 разрешимы по Тьюрингу. c) Либо L либо L 0 принимается некоторой машиной Тьюринга, но не разрешим по Тьюрингу. 4.4 Проблемы неразрешимости для контекстно- свободных языков Определение 43. Пусть ? алфавит. Обозначим через P множе- ство упорядоченных пар непустых строк (u 1 , v 1 ), (u 2 , v 2 ), . . . , (u m , v m ) из символов ?. То есть P конечное подмножество ? ? Ч ? ? . Решение P строка w, для которой существует такая последовательность пар (u i 1 , v i 1 ) , (u i 2 , v i 2 ) , . . ., (u i m , v i m ) , что w = u i 1 u i 2 · · · u i m = v i 1 v i 2 · · · v i m Проблема соответствий Поста определить, существует ли ре- шение. Определение 44. Пусть ? алфавит. Обозначим через P множе- ство упорядоченных пар непустых строк (u 1 , v 1 ), (u 2 , v 2 ), . . . , (u m , v m ) из символов ? вместе со специальной парой. (u 0 , v 0 ) . В модифицирован- ной системе соответствий, решение P такая строка w, что суще- ствует последовательность пар (u 0 , v 0 ) , (u i 1 , v i 1 ) , (u i 2 , v i 2 ) , . . ., (u i m , v i m ) , w = u 0 u i 1 u i 2 · · · u i m = v 0 v i 1 v i 2 · · · v i m . Модифицированная проблема соответствий Поста определить, существует ли решение для мо- дифицированной системы соответствий. Лемма 15. Если разрешима проблема соответствий Поста, то разре- шима и модифицированная проблема Поста. 58 Глава 4. Машина Тьюринга Доказательство. Пусть P 1 модифицированная система соответствий (u 0 , v 0 ) , (u 1 , v 1 ) , (u 2 , v 2 ) , . . ., (u m , v m ) . Пусть символы $ и ? не принадле- жат ?. Для строки w = a 1 a 2 a 3 · · · a k , определим L(w) = ?a 1 ?a 2 ?a3?· · ·?a k и R(w) = a 1 ? a 2 ? a 3 ? · · · ? a k ? . Пусть P 2 содержит пару (L(u 0 ), L(v 0 )?) , и для остальных пар (u, v) ? P 1 , пусть (L(u), R(v)) ? P 2 . Кроме того, включим в P 2 пару (?$, $). Очевидно, что только (L(u 0 ), L(u 0 )?) может начинать решение P 2 , так как это единственная пара, в которой одно слово не начинается с ?, а другое начинается. Также очевидно, что единственная пара, заканчивающая решение P 2 (?$, $), поскольку это единственная пара, в которой последние символы совпадают. Пусть существует такое семейство пар (u 0 , v 0 ) , (u i 1 , v i 1 ) , (u i 2 , v i 2 ) , . . ., (u i m , v i m ) , что w = u 0 u i 1 u i 2 · · · u i m = v 0 v i 1 v i 2 · · · v i m . Тогда последователь- ность (L(u 0 ), L(v 0 )) , (L(u i 1 ), R(v i 1 )) , (L(u i 2 ), R(v i 2 )) , . . ., (L(u i m ), R(v i m )) , (?$, $) порождает решение w 0 = L(u 0 )L(u i 1 )L(u i 2 ) · · · L(u i m ) ? $ = L(v 0 ) ? R(v i 1 )R(v i 2 ) · · · $ в P 2 . Строки L(u 0 )L(u i 1 )L(u i 2 ) · · · L(u i m ) ? $ и L(v 0 ) ? R(v i 1 )R(v i 2 ) · · · $ в P 2 отличаются от строк u 0 u i 1 u i 2 · · · u i m и v 0 v i 1 v i 2 · · · v i m в P 1 , соответственно, наличием ? между букв и $ в конце слова. Следовательно, поскольку решение модифицированной системы со- ответствий Поста влечет решение системы соответствий Поста, разре- шимость проблемы соответствий Поста влечет разрешимость модифи- цированной проблемы соответствий Поста. Теорема 37. Проблема соответствий Поста неразрешима. Доказательство. Докажем, что разрешимость модифицированной про- блемы Поста влечет существование машины Тьюринга, принимающей L 0 из предыдущего параграфа. По строке, соответствующей данной машине Тьюринга M и слову w, построим систему соответствий Поста, которая имеет решение ? M принимает w. Начинаем с пары (], ]s 0 w) , ] ]s 0 w Для каждого символа X ? ? положим X X Для каждого состояния s, которое не является конечным, каждого состояния s 0 , и символов X, Y , Z ? ?, введем sX Y s 0 , если ?(s, X) = (s 0 , Y, R) XsY s 0 XZ , если ?(s, Y ) = (s 0 , Z, L) s] Xs 0 ] , если ?(s, ]) = (s 0 , X, R) 4.4. Проблемы неразрешимости для контекстно-свободных языков 59 Xs] s 0 XY ] , если ?(s, ]) = (s 0 , Y, L) Назовем эти строки строками, порожденными ?. Кроме того, добавим правила (0s m 0, s m ) , (1, 1), (], ]), (0s m 1, s m ) , (1s m 0, s m ) , (1s m 1, s m ) , (0s m , s m ) , (s m 0, s m ) , (1s m , s m ) , (s m 1, s m ) , (s m ]], ]) Пусть существует семейство последовательностей, описывающих при- нятие строки s машиной M, пользуясь индукцией по числу вычислений, покажем существование частичного решения ]s 0 w]? 1 s 1 ? 1 ]? 2 s 2 ? 2 ] . . . ]? n?1 s n?1 ? n?1 ] ]s 0 w]? 1 s 1 ? 1 ]? 2 s 2 ? 2 ] . . . ]? n?1 s n?1 ? n?1 ]? n s n ? n ] Для n = 0 имеем ] ]s 0 w . Пусть дано ]s 0 w]? 1 s 1 ? 1 ]? 2 s 2 ? 2 ] . . . ]? k?1 s k?1 ? k?1 ] ]s 0 w]? 1 s 1 ? 1 ]? 2 s 0 ? 2 ] . . . ]? k?1 s k?1 ? k?1 ]? k s k ? k ] Используем одно из ?-правил, чтобы продлить верхнюю строку на ? k s k ? k ] Если мы не достигаем конечного состояния, мы не имеем решения. Если мы достигнем конечного состояния, то мы получим и решение. Следова- тельно, если проблема соответствий Поста разрешима, то и L 0 разрешим. Так как последнее неверно, то и проблема Поста неразрешима. Теорема 38. Проблема проверки L(G 1 ) T L(G 2 ) = ? неразрешима для двух контекстно-свободных грамматик G 1 и G 2 Доказательство. Пусть P ? ? ? Ч ? ? произвольное семейство состо- яний (u 0 , v 0 ) , (u 1 , v 1 ) , (u 2 , v 2 ) , . . ., (u m , v m ) . Обозначим далее через w ?1 слово w в обратном порядке. Пусть G 1 порождена правилами S ? u i Cv ?1 i , i = 1, . . . n. C ? u i Cv ?1 i , i = 1, . . . n. C ? c. Следовательно, каждое слово L(G 1 ) имеет вид u i 0 u i 1 u i 2 · · · u i m cv ?1 i m · · · v ?1 i 2 v ?1 i 1 v ?1 i 1 Пусть L(G 2 ) = {wcw ?1 |w ? ? ? } . Тогда w ? L(G 1 ) T L(G 2 ) ? w = u i 0 u i 1 u i 2 · · · u i m = v i 0 v i 1 v i 2 · · · v i m , что есть решение проблемы соответ- ствий Поста. Следовательно, задача проверки L(G 1 ) T L(G 2 ) = ? нераз- решима для произвольной пары контекстно-свободных грамматик. Определение 45. Контекстно-свободная грамматика переопределе- на если существует два независимых левых вывода одного и того же слова. 60 Глава 4. Машина Тьюринга Теорема 39. Проблема выяснения переопределенности грамматики нераз- решима. Доказательство. Пусть P ? ? ? Ч ? ? произвольное семейство состо- яний (u 0 , v 0 ) , (u 1 , v 1 ) , (u 2 , v 2 ) , . . ., (u n , v n ) . Пусть ? 0 , ? 1 , ? 2 , . . . , ? n сим- волы не из ?. Построим две грамматики G 1 и G 2 по правилам: G 1 = (N 1 , ? ? , S 1 , P 1 ), где N 1 = {S 1 } , ? ? = ? S{? 0 , ? 1 , ? 2 , . . . , ? n } , и P 1 = {S 1 ? ? i S 1 u i |i = 0, 1, . . . , n} S{S 1 ? ?} G 2 = (N 2 , ? ? , S 2 , P 2), где N 2 = {S 2 } , ? ? = ? S{? 0 , ? 1 , ? 2 , . . . , ? n } , и P 2 = {S 2 ? ? i S 2 v i |i = 0, 1, . . . , n} S{S 2 ? ?} Очевидно G 1 и G 2 не переопределены. Пусть G = (N, ? ? , S, P ) , где N = {S, S 1 , S 2 } и P = P 1 S P 2 S{S ? S 1 , S ? S 2 } . Если существует решение, одно правило начинается с S ? S 1 , а другое с S ? S 2 , то есть G переопределена. Пусть наоборот, G переопределена, тогда u i 0 u i 1 u i 2 · · · u i m = v i 0 v i 1 v i 2 · · · v i m и существует решение. Следовательно, решение проблемы соответствий Поста суще- ствует ? контекстно-свободная грамматика переопределена. Задачи 1. Доказать, что класс языков, принимаемых машинами Тьюринга за- мкнут относительно операции объединения. 2. Доказать, что класс языков, принимаемых машинами Тьюринга замкнут относительно операции пересечения. 3. Доказать, что класс языков, разрешимых по Тьюрингу, замкнут относительно операции пересечения. 4. Доказать, что класс языков, разрешимых по Тьюрингу, замкнут относительно операции объединения. 5. Доказать, что класс языков, разрешимых по Тьюрингу, замкнут относительно операции конкатенации. 6. Доказать, что класс языков, принимаемых машинами Тьюринга замкнут относительно операции замыкания Клини. 7. Доказать, что неразрешима проблема выяснения для данных ма- шины Тьюринга M и строки w, принимает ли M все свои состояния в процессе обработки w. 8. Доказать, что проблема проверки тождества L(?) = ? ? неразре- шима для любой контекстно-свободной грамматики ?. 4.4. Проблемы неразрешимости для контекстно-свободных языков 61 9. Доказать, что проблема проверки тождества L(?) = L(? 0 ) нераз- решима для произвольной пары контекстно-свободных грамматик ?, ? 0 10. Доказать, что не существует алгоритма, позволяющего опреде- лить, бесконечно ли пересечение языков двух контекстно-свободных грам- матик. 11. Доказать, что не существует алгоритма, позволяющего опреде- лить, бесконечно ли дополнение языка контекстно-свободной граммати- ки. 62 Глава 4. Машина Тьюринга Литература [1] J. A. Anderson, Automata theory with modern applications, Cambridge University Press, 2006. [2] Ю. Г. Карпов, Теория автоматов, Питер, 2002. [3] Д. Хопкрофт, Р. Мотвани, Д. Ульман, Введение в теорию автома- тов, языков и вычислений. Второе издание, Вильямс, 2010. 63 |