Вопросы к экзамену (2009)

Вопросы к экзамену по конструлям (2009)1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20.21.22.23.24.25.26.27.28.29.30.31.32.33.34.35.36.37.38.39.40.41.42.43.44.45.46.47.48.49.50.51.52.53.54.55.56.Определение грамматик типа 0 по ХомскомуОпределение грамматик типа 1 (неукорачивающих) по ХомскомуОпределение детерминированной машины ТьюрингаОпределение недетерминированной машины ТьюрингаОпределение конфигурации машины ТьюрингаОпределение языка, допускаемого машиной ТьюрингаСоотношение между языками, порождаемыми грамматиками типа 0 и языками, допускаемыми машинамиТьюрингаОбъяснить разницу между недетерминированной и детерминированной машиной ТьюрингаОпределение регулярного множестваОпределение регулярного выраженияОпределение праволинейной грамматикиОпределение недетерминированного конечного автоматаОпределение детерминированного конечного автоматаОбъяснить разницу между недетерминированным и детерминированным конечным автоматомОпределение конфигурации конечного автоматаОпределение языка, допускаемого конечным автоматомОпределение е-замыкания для подмножества состояний НКАОпределение расширенной функции переходов для ДКАОпределение расширенной функции переходов для НКАОпределение функции firstpos для поддерева в дереве регулярного выраженияОпределение функции lastpos для поддерева в дереве регулярного выраженияОпределение функции followpos для позиций в дереве регулярного выраженияСформулировать соотношение между регулярными множествами и языками, допускаемыми КАОпределение регулярной грамматикиСформулировать соотношение между языками, порождаемыми праволинейными грамматиками иязыками, допускаемыми КАОпределение эквивалентных состояний ДКАОпределение различимых состояний ДКАОпределение контекстно-свободной грамматики без е-правилОпределение контекстно-свободной грамматикиОпределение вывода в КС-грамматикеОпределение языка, порождаемого КС-грамматикойОпределение сентенциальной формыОпределение однозначной КС-грамматикиОпределение неоднозначной КС-грамматикиОпределение недетерминированного МП автоматаОпределение детерминированного МП автоматаОпределение конфигурации МП автоматаОпределение языка, допускаемого МП автоматомЧто означает, что недетерминированный МП автомат допускает опустошением магазинаСоотношение, между языками, порождаемыми КС-грамматиками, и языками, допускаемыминедетерминированными МП автоматамиФормулировка леммы о разрастании для КС-языковОпределение нормальной формы Хомского для КС-грамматикиОпределение правостороннего вывода в КС-грамматикеОпределение левостороннего вывода в КС-грамматикеКакая грамматика называется леворекурсивной?Определение множества FIRST1Определение множества FOLLOW1Определение LL(1) ГрамматикиОпределение LR(1) ситуацииОпределение LR(1) грамматикиКакого типа конфликты могут появиться в канонической системе множеств LR(1) ситуаций?Определение конфигурации LR-анализатораКак меняется конфигурация LR-анализатора при действии reduce?Какие типы действий выполняет LR-анализатор?Как меняется конфигурация LR-анализатора при действии shift?Что такое основа правой сентенциальной формы.