Гладкий - Формальные грамматики и языки - 1973 (947381), страница 10
Текст из файла (страница 10)
Сопоставим каждой цепочке в ш !" число ч(в) следующим образом: ч(Л) = О; ч(а, ... ас )=Сг" ' ° сс+ ... + й ° С„я+ 3 ° С„!+ С„, (Не смел шнвать с обычным представлением натурального числа в системе счисления! В чем разница?) Показать, что ч — взаимно однозначное отображение У» на Ас = (О, 1, ...) и что ч(ф) ( ч(ф) тогда и только тогда, когда ф предшествует ф в смысле стандартного порядка, отвечающего пересчету аь , аь.
1.4. а) Доказать, что С.(Е! 0 Ез) = ЕЕ~ () С.Е», (Ес () Ез)Е ~ 1.1 Е () Е,Е. б) Имеют ли место аналогичные тождества для пересечения? 1.3. Сформулировать строгие (индуктивные) определения много- члена н регулярного выражения. 1.б. Представить с помощью бескоэффициентных регулярных выражений от языков (а1)...., (а,), (Л): а) множество цепочек, содержащих вхождения данной непустой цепочки в ас ... ас ! с ю б) множество цепочек, начинающихся (оканчивающихся) вхождением данной непустой цепочки в = а ... а !» в) множество цепочек, не содержащих вхождений цепочки в=а! " ас' г) множество цепочек, содержащих ровно й вхождений цепочки ас ас » 1.7. Показать, что для всякого регулярного выражения ф($П ..., Ев) найдется такое выражение ф($Г ..., $ )= )(дс($с, .", $х), ° ° ., й ($с, °, $а), $с, ..., $а) (з~)О), где а„..., д» вЂ” многочлены, что для любых й языков каждый из которых содержит пустую цепочку, ф(Еп ..., Еь) = ф (Ес, ..., Ез).
При этом, если ф не содержит коэффициентов, то это же верно для Е дг ..., К» 1.8. Выразить объединение, умножение и итерацию языков через подстановку. 1.9. Для того, чтобы каждому выводу в грамматике Г соответствовал единственный размеченный вывод, необходимо и достаточно, чтобы схема Г не содержала правил фс -»фп ф,-»ф,, удовлетворяющих одному из следующих двух условий (!) ЗвВв' „-Л Л Р,= Р,в'Л ф,= вф,в); (и) Вф',ВфзВЗЕВЕ(ф!'= ф',Гйф; = еф, л (ф, =' ф,е ла р, ='еф, ч 'ф! -' ф,е л'ф, = еф,) л ф,ф,'~ л). Доказвтсч 1.10.
Назовем характеристикой вывода [Стоцкий !967] *) последовательность применяемых в этом выводе правил; аналогично дли размеченного вывода. (Размеченный вывод имеет, очевидно, единственчую характеристику.) Показать, что в грамматике тогда и только тогда существуют различные размеченные выводы с одинаковыми характеристиками, отвечающие одному н тому же выводу, когда ее схема содержит правило вида ф — ф" (т, л = О, 1, ...).
1.11. Могут ли полные выводы в одной и той же грамматике, оканчивающиеся разными цепочками, иметь одинаковые характеристики? 1.12. Назовем вывод в грамматике Г= (У, 97, С, )7) приведеннымы м н а лево, если на каждом его шаге соответствующее правило применяется к самому левому вхоскдснню своей левой части .
(прн подходящей разметке вывода). Множество цепочек из У*, выводимых в Г из! с помощью выводов, приведенных налево, обозначим Ел (Г). Показать, что: а) для произвольной грамматики Г можно построить'*) такую грамматику Г', что Е(Г) = Ел(Г'); если при этом à — НС-грамма. тика, то и Г' можно сделать НС-грамматикой; б) если à — Б-грамматика, то Е(Г) = Ел (Г). 1.13. Назовем грамматикой со стоп-и р а вила и и упорядоченную четверку л = (У, Е с(, сс'), где У вЂ” конечное множество, ! ш У, Й вЂ” конечное множество правил такого 'же вида, как правила обычной грамматики, я Сг' — подмножество !т («множество стоп-правил»).
Вывод в Л (вывод определяется, как для обычной грамматини) назовем 1-выводом, если в нем применяются только правила нз !т — )(' и к его последней цепочке никакое правило нз !с не применимо, и 2-выводом, если на всех его шагах, кроме последнего, применяются правила из С! — С!', а на последнем — правило нз СГ'. Множество цепочек, выводимых из! с помощью 1-(2-) выводов, обозначим Е1(Л) (1.,(Л)). Показать, что: а) для любой грамматики Г можно построить такие грамматики со стоп-правилами Л, Ль Ль что с-(Г) = Е1(Л) [) Ез(Л) = Ес(Л,) = = Ез(Л«); б) для любой грамматики со стоп-правилами Л можно построить такие грамматики Г Гь Г«, что Ес(Л) 0 Ез(Л) = Е(Г) Ес(Л) = = Е(Г,), Е,(Л) = Е(Г',).
' [Рг!1 !966). 1.14. Построить А-грамматики, порождающие: а) множество всевозможных цепочек в словаре У = (аь ... ..., а»), содержащих вхождения данной цепочки х=а! ... ас (со. 3» ответственно содержащих не менее л вхождений х, начинающихся вхождением х, оканчивающихся вхождением х, не содержащих вхождений х, содержащих ровно л вхождений х); б) язык У+ = (х [ х гж У, ) х [ ) л); в) язык С'Ез, где Ез — произвольный конечный язык в У; ') В этой работе используется теРмин цепочка вывода. '") См.
сноску на стр. 32. упражнения (гл. г основные понятия г) язык У+» (х]х«э У, ]х]=з1+1, 1=0, 1, ...) (з,1)1); д) язык а" а~ ... а'~, г е где ао ..., а„ вЂ” произвольные напу- стые цепочки в У. 1.15. П . Построить Б-грамматики, порождающие: ваний а) множество правильно построенных формул логики высказы-, ременных); в обычной «скобочной» записи (с фиксирован б нпым на ором пеб) то же для логики преднкатов; в) то же, что а), для бесскобочной записи; г) то же, что б), для бесскобочной записи; и) «язык Дика» В Д ь — множество всех цепочек в алфав те а, ,, ..., ), равных единице в свободной группе со свои боднымн об аз ю нми р уюшнми ап ..., аа (т. е. таких, которые могут быть преобразованы Л в последовательным вычеркиванием вхождений подцепочек вида а;а~ и агаг (ср.
ниже, 9 6.5). 1Аб. Аб. Для каждого из языков упражнений 124 и 1.15 допускающую его Э-машину. и . и . построить 1.17. Пос троить ДЭ-машины, распознающие сле ю и множества (в простейшей записи): дующие числовые а) множество четных чисел; б) произвольную арифметическую прогрессию; в) множество полных квадратов.
1.18. Пост роить ДЭ-машины, вычисляющие функции: а) 1(х) = хс(х (с( — фиксированный символ); б) ((х) = хгх» (ха — фиксированная цепочка). р стандартная нумерация словаря 1.19. Пусть т — некого ая ст а) т(х); остроить ДЭ-машины, вычисляющие следующле ф ле функции: б) т '(и); в) т '(т(х)+1); г) ~1(х), принимающую для каждой цепочки ви а х, у щ У', значение т-' (т (х) + т (у)); чки вида хбу, где х,у~аУ', д) у (з), принимаю ю ля а ', значение т- (т (х) ° т (у)), щу д к ждой цепочки вида хбу, где 120. Машину Тью инга р га с неэластичной рабочей р делить так же, как Э-машину, -ма ш пну) можно оп е е символом» )с н инструкции (') ся азнице, что рабочий алфавит опо н ) ) заменяются янструп ции видов (и) й пн а 46 где уауршд, А, Вш5»ОЯ; такая инструкция означает замену в обозреваемой й символа А на символ В (без сдвига головки) и пе о ячейке абочей ниЯ яп в состоЯние 45.
вкн) и переход из состоя- Одиоленточная машина Тьюринга с неэластичной лентой (ОН-машина) отличается от Н-машины отсутствием входной ленты, входной головки, входного алфавита и инструкций типа (1). Детерминированные Н- и ОНмашины (ДНмаш н н ы, ДОН-и а ш н н ы) определяютсп очевидным образом. (Машины Тьюринга, обычно рассматриваемые в курсах теории алгоритмов, — это ДОН-машины со следующим дополнительным аграниче. пнем: каково бы ни было незаключнтельное состояние ф программа машины либо содержит инструкцию (типа (1т) илн (т)) с левой частью ф либо для каждого А ш йг содержит инструкцию (типа (гл)) с левой частью Аф) Ситуация, вычисление и х-вычисление для Н-машины опреде.
ляются точно так же, как для Э-машины. Начальная н заключительная х-ситуация тоже определяются аналогично тому, как это делается для Э-машины, но последней компонентой вместо че будет 4г»», где й — произвольное натуральное число. х-вычисление н полное х-вычисление можно определить теперь так же, как для Э-ма.
шины; (х, у]-вычнслением (у ш %") естественно назвать х-вычисление, оканчивающееся ситуацией вида (41, тзтьх, ф Л Ау У)с ) (Ч('а Оа) Допускание языка н вычисление функции Н-машиной определяется так же, как для Э-машины. Для ОН-машнны ситуация определяется как тройка (Оа х', х«) (обозначения сохраняют прежний смысл); язык Ь а; йт» допускается, если нычисление, начинающееся ситуацией вида (дь Л, хУ) и оканчивающееся ситуацией вида (дп Л, Х») (дг ш О») существует тогда и только тогда, когда х ш т'.; ДОН-машнна вычисляет функцию йп 1.— йг*(т. ш 5»»), если вычисление, начинающееся ситуацией вида (дь Л, хУ) и оканчивающееся ситуацией вида (уп Л, уй") (ут'ш й»), существует тогда и только тогда, когда у = у(х).
' а) Перенести на Н- и ОН-машины теорему 1.2, б) Перенестн теорему 1.3 на ДН- и ДОН-машины, а также на ДОН-машины с указанным выше дополнительным ограничением. в) Показать, что классы языков, допускаемых Эь Нч ДНч ОН- н ДОН-машинами, а также ДОН-машннами с вышеуказанным ограничением, совпадают, причем для всякой машины наждого из перечисленных классов можно построить эквивалентную ей машину любого другого класса. 1.21.
Назовем Э-машину числовой, если ее входной алфавит состоит из единственного символа ], Язык, допускаемый (функцию, вычисляемую) числовой Э(ДЭ)-машиной, назовем ч и с л о в ы м р екурсивно перечислим ым множеством (ч.р.п.м), соответственно числовой частично рекурсивной функцией (ч.ч.р.ф.). Для произвольного алфавита У назовем язык Ьшу' нумерациоино рекурсивно перечислнмым множеством (н.р.п.м) и функцию 1: Т-» У» (Т<: — У') нумерациоино частично рекурсивной функцией (н ч,р, ф.), если существует такая стандартная нумерации т алфавита У, что для некоторого ч. р.и. м, 5' имеет место ь' = т(Ц вЂ” соответственно для некоторой ч.ч.р.ф.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
