Сканы теоретического минимума (1131606)
Текст из файла
Конструлиторы-2009 — теоретический минимум согпр11ес1 Ьу пехог Й 1ео.гпоп1е)сЫ есИес1 Ьу жс$ог ч. 1.1 Ье1а 1. Определение грамматик типа 0 по Хомскому Пусть дана грамматика С = (Ф Т Р о). Тогда если прав 1 ) 1 если правила грамматики не удовлетвотипа, или грамматикой , ряют никаким ограничениям, то ее называют грамматикой О бвв ограничений.
2, О пределение грамматик типа 1 (неукорачивающих) по Хомскому Если а) каждое правило грамматики, кроме о' — + е, имеет вид а -+ р, где ~а~ < ф, 'и б) в том случае, когда о — 'е Е Р символ о не встречает ся в правых частях правил, то грамматику называют грамматикой типа 1, или нвукорачиваюсцеи. 3. О . Определение детерминированной машины Тьюринга Детерминированная машина Тьюринга — Т = © Г, Е, О; до, Р), где ° Я вЂ” конечное множество состояний, ° à — конечное множество символов (конечный алфавит1 1 ° Š— входной алфавит, Е С Г ~ (е) (в - пустой символ),- е Ю вЂ” правила перехода. В: Щ '1 Р) х Г -+ С„~ х Г х 1Х, Вг, ° до Е Я = начальное состояние, ° Р С Я вЂ” множество конечных состояний.
4. Определение недетерминированной машины Тьюринга Недетерминированная машина Тьюринга — Т = Я, Г, Е,.0, оо, Р): е Ц вЂ” конечное множество состояний, ° à — конечное множество символов (конечный алфавит), ° Š— входной алфавит, Е С Г ~ (е) (е - пустой символ), ° .Π— правила перехода. О: Я ~ Р) х Г -+ 2О" г" Сь н1 е до 6 Я вЂ” начальное состояние, ° Р С Я вЂ” множество конечных состояний. 5. Определение конфигурации машины Тьюринга Конфигурацией машины Тьюринга называется тройка (д, ти, г), где ° д е Я вЂ” состояние машины Тьюринга, ° и е Г~~ — вход, помещаемый на ленту машины Тьюринга, и> = а1... а„, ° 1 е Я вЂ” положение головки машины Тьюринга.
б. Определение языка, допускаемого машиной Тьюринга Язык, допускаемый машиной Тьюринга — множество таких слов и, что, машина Тьюринга, находясь в состоянии (дш и, 1) может достигнуть через конечное число переходов состояния о е Р. 7. Соотношение между языками, порождаемыми грамматиками типа 0 и языками, допускаемыми машинами Тьюринга. Класс языков, допускаемых машиной Тьюринга, эквивалентен классу языков, порождаемых грамматиками типа О. 8. Объяснить разницу между недетерминированной и детерминированной ма-. шиной Тьюринга. Детерминированная машина Тьюринга из данного состояния по данному символу может сделать не более одного-перехода, недетерминированнал же таким свойством не обладает. 9. Определение регулярного множества Регуллрное множество в алфавите Т определяется рекурсивно следующим образом: (1) 6 (пустое множество) — регулярное множество в алфавите Т; (2) (е) — регулярное множество в алфавите Т (е — пустая цепочка); (3) (а) — регулярное множество в алфавите Т для каждого а Е Т; (4) если Р и Я = регулярные множества в алфавите Т, то регулярными являются и множества (а) Р 0 Я (объединение), (б) РЯ (конкатенация, т.е.
множество (рддр б Р, д Е Я) ), (в) Р* (итерация: Р' = Ц~ р Р" );. (5) ничто другое не является регулярным множеством в алфавите Т 10. Определение регулярного выражения Регулярное выражение в алфавите Т и обозначаемое им регулярное множество в алфавите Т определяются рекурсивно следующим образом: (1) 9 — регулярное выражение, обозначающее множество 9; (2) е — регулярное выражение, обозначающее множество (е); (3) а — регулярное выражение, обозначающее множество (а); (4) если р и о — регулярные выражения, обозначающие регулярные множества Р и Я соответственно, то (а) (р~д) — регулярное выражение, обозначающее регулярное множество Р 0 Я, (б) (рц) — регулярное выражение, обозначающее регулярное мно жество РЯ, (в) (р') — регулярное выражение, обозначающее регулярное множество Р" (5) ничто другое не является регулярным выражением в алфавите Т.
11. Определение праволинейной грамматики Если каждое правило грамматики имеет вид либо А -+ хВ, либо А -+ х, где А, В е У, х Е Т*, то ее называют грамматикой типа 3, или праволинебной. 12. Определение недетерминированного конечного автомата Недетерминированньт" конечный автомат(НКА) — это пятерка М = (Я, Т, Х?,Е1, Г), где (1) Я вЂ” конечное множество состояний; (2) Т вЂ” конечное множество допустимых входных символов (входной алфавит); (3) .0 — функция переходов (отображающая множество Я х (Т 0 (е)) во множество подмножеств множества Я), определяющая поведение управляющего устройства; ( ) до Е ~~ — начальное состояние управляющего устройства; (4) (5) Г С Я вЂ” множество заключительных состояний. 13. О 3. Определение детерминированного конечного автомата Пусть М = (~ Т .0 Г)- — (О...оо, ) - НКА. Будем называть М детерминированным конечным автоматом (ДКА), если выполнены следующие 2 условия: (1) Р(д, е) = И для любого д Е Я, и ( ) (д, ) с держит не более одного элемента для любых д Е Я и а Е Т.
14. Объяснить азии ме р цу жду недетерминированным и детерминированным конечным автоматом См. определение ДЛА 1б. Определение конфигурации конечного автомата ПустьМ=(О ТР Г) — Н = (О... до, ) — КА. Конфигурацией автомата М называется пар ( ) ЯхТ" ге , д д — текущее состояние управляющего устройства а и— — тсяпара д,ю Е , а и — цепочка символов и всех символов справа от него. на входной ленте, состоящая из символа под головкой Конфигурация (до, в) называется начальной, а конфигурация (д, е), где д Е Г -заключительной (или допускающей) . 1 . Определение языка, допускаемого конечным автоматом 16. О Автомат М допускает цепочку м, если (оо,м) 1-' (о, «)для некоторого Е Г..
Я д у ~м автоматом М, называется 'множество входных цеп д .. зыком, ц очек, допускаемых автоматом М, то есть: ~(~) — ("! 0~ Е Т и (Чо, ~о) ~- (д, «) для некоторого д Е Г1 17. Определение «-замыкания для подмножества состояний НКА «-замыкание множества состояний В Л С Я вЂ” множеств — ножество состояний НКА, достижимыхиз состояний вхо хв Л дящи Л, посредством только переходов по «, то есть множество 8 = ~ ~ (р ~ (д, «) 1 * (р, «) ) 18. Определение расширенной функции переходов для ДКА Р' - расширенная функция переходов автомата М:: Р'(д, ы) = р, где ш Е Т', тогда и только тогда, когда (д, ы) 1-" (р, е). 19.
Определение расширенной функции переходов для НКА Расширенная функция переходов НКА Р1 . Я х Т* — ~ 2О определяется следующим образом: Р1(д, «) = ес1ооиге((д~) РДд, и~а) = ес1оэиге( Д Р(р, а)),ш Е Те, а Е Т р«.01(д,ю) 20. Определение функции йгвФров для подцерева.в дереве регулярного выражения. Функция ~ггз1роз(п) для каждого узла и синтаксического дерева регулярного выражения дает множество позиций, которые соответствуют первым символам в подцепочках, генерируемых подвыражением с вершиной в и. 21. Определение функции 1авФров для поддерева в дереве регулярного выражения. 1а88роэ(п) дает множество позиций, которым соответствуют последние символы в подцепочках, генерируемых подвыражениями с вершиной и.
22. Определение функции 1о11о юров для позиций в дереве регулярного выраже- ния. Если 1 — позиция, то 3'о11огороэ(г) есть множество позиций 3 таких, что существует некоторая строка ... сс1 ..., входящая в язык, описываемый регулярным выражением,—. такая, что позиция г соответствует этому вхождению с, а позиция у — вхождению д. 23. Сформулировать соотношение между регулярными множествами и языка- ми, допускаемыми КА.
Любой конечный автомат распознает регулярное множество цепочек символов входного алфавита. Верно и обратное — для любого регулярного языка можно построить распознающий его конечный автомат. 24. Определение регулярной грамматики Регулярные грамматики — праволннейные (А — > ю, А — гоВ,ю Е Т"), леволинейные (А — + и,А-+ Вга,го Е Т'). 25. Сформулировать соотношение между языками, порождаемыми праволинейными грамматиками и языками, допускаемыми КА.
Для любой праволинейной грамматики существует конечный автомат, проверяющий порождаемый грамматикой язык. Для любого конечного автомата существует праволинейная грамматика, порождающая проверяемый конечным автоматом язык. 26. Определение эквивалентных состояний ДКА Говорят, что слово и рэлличает состояния р и д детерминированного конечного автомата (ц', Т, О, ао, Р), если одно из состояний 33(р, и), В(д, го) заключительное, а "другое не является заключительным. Состояния р и д ДКА называются эквпвааенпгиими, если не существует слова, различающего их. 27. Определение различимых состояний ДКА Состояния р и д детерминированного конечного автомата Я, Т,.0, до, Р) называются различимыми, если существует слово га, которое их различает. 28.
Определение контекстно-свободной грамматики без е-правил Любое правило контекстно свободной грамматики без е-правил имеет вид: А — а, о б (У 0 Т)', допускается наличие правила о' -+ е, если о' не входит ни в какую правую часть правил. 29. Определение контекстно-свободной грамматики Если каждое правило грамматики имеет вид А — 33, где А Е М,,д б (РОТ)*, то ее называют грамматикой типа 2, или,коитиекстно свободной граммагпикой (КС-грамматикой). 30. Определение вывода в КС-грамматике Определим на множестве (М 0 Т)' грамматики С = (Ф, Т, Р, Я) бинарное отношение выводимости " ~а следующим образом: если б -+ 7 ~ Р, то об~3 =~ о7~3 для всех а,13 Е (Ф 0 Т)'.
Если о1 =~ аг, то аг непосредственно выводима из аь Если о =~" 33(й > О), то существует последовательность шагов 7о ~ 71 =~ 7г =~ =~ 7ь — 1 =~ 7ь где а = 7о и,8 = 7 . Последовательность цепочек 7о,7ь 7г,...,7ь ь 7ь в этом случае называется выводом Д из о. 31. Определение языка, порождаемого КС-грамматикой Языком, порождаемым грамматикой 0 = (Ф, Т, Р, о) (обозначается ЦС)) называется множество всех цепочек терминалов, выводимых из аксиомы, то есть: ЦС) = (п>~п> е Т*> Я =~+ и>) 32. Определение сентенциальной формы Сентенциальная форма — цепочка (состоящая, в общем случае, из терминалов и нетерминалов), выводимая из аксиомы грамматики.
33. Определение однозначной КС-грамматики КС грамматика называется однозначной или детерминированной, если всякая выводимая терминальная цепочка имеет только одно дерево вывода (соотвественно только один левый и только один правый вывод). 34. Определение неоднозначной КС-грамматики КС-грамматика С называется неоднозначной, если существует хотя бы одна цепочка о с Х(С), для которой может быть построено два или более различных деревьев вывода. 35. Определение недетерминированного МП автомата Недетерминированный автомат с магазинной памятью (МП-автомат) — семерка ЛХ = © Т, Г, Р, до, Яш г), где (а) Я вЂ” конечное множество состояний, представляющее всевозможные состояния управляющего устройства, (Ь) Т вЂ” конечный входной алфавит, (с) à — конечный алфавит магазинных символов, (4) Р— отображение множества (,> х (Т> > Я) х Г в множество всех конечных подмножеств Я х Г", называемое функцией переходов, (е) >ус Е Я вЂ” начальное состояние управляющего устройства, (Г) Еэ е à — символ, находящийся в магазине в начвльньгй момент (начальный символ магазина), ® Р С Я вЂ” множество заключительных состояний.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
