Конструирование Компиляторов, Теоретический минимум (2009)

Материал из eSyr's wiki.

см. также ответы на вопросы теоретического минимума 2007 года, список определений.

1. Определение грамматик типа 0 по Хомскому
2. Определение грамматик типа 1 (неукорачивающих) по Хомскому
3. Определение детерминированной машины Тьюринга
4. Определение недетерминированной машины Тьюринга
5. Определение конфигурации машины Тьюринга
6. Определение языка, допускаемого машиной Тьюринга
7. Соотношение между языками, порождаемыми грамматиками типа 0 и языками, допускаемыми машинами Тьюринга
8. Объяснить разницу между недетерминированной и детерминированной машиной Тьюринга
9. Определение регулярного множества
10. Определение регулярного выражения
11. Определение праволинейной грамматики
12. Определение недетерминированного конечного автомата
13. Определение детерминированного конечного автомата
14. Объяснить разницу между недетерминированным и детерминированным конечным автоматом
15. Определение конфигурации конечного автомата
16. Определение языка, допускаемого конечным автоматом
17. Определение ε-замыкания для подмножества состояний НКА
18. Определение расширенной функции переходов для ДКА
19. Определение расширенной функции переходов для НКА
20. Определение функции firstpos для поддерева в дереве регулярного выражения
21. Определение функции lastpos для поддерева в дереве регулярного выражения
22. Определение функции followpos для позиций в дереве регулярного выражения
23. Сформулировать соотношение между регулярными множествами и языками, допускаемыми КА
24. Определение регулярной грамматики
25. Сформулировать соотношение между языками, порождаемыми праволинейными грамматиками и языками, допускаемыми КА
26. Определение эквивалентных состояний ДКА
27. Определение различимых состояний ДКА
28. Определение контекстно-свободной грамматики без е-правил
29. Определение контекстно-свободной грамматики
30. Определение вывода в КС-грамматике
31. Определение языка, порождаемого КС-грамматикой
32. Определение сентенциальной формы
33. Определение однозначной КС-грамматики
34. Определение неоднозначной КС-грамматики
35. Определение недетерминированного МП автомата
36. Определение детерминированного МП автомата
37. Определение конфигурации МП автомата
38. Определение языка, допускаемого МП автоматом
39. Что означает то, что недетерминированный МП автомат допускает опустошением магазина
40. Соотношение, между языками, порождаемыми КС-грамматиками, и языками, допускаемыми недетерминированными МП автоматами
41. Формулировка леммы о разрастании для КС-языков
42. Определение нормальной формы Хомского для КС-грамматики
43. Определение правостороннего вывода в КС-грамматике
44. Определение левостороннего вывода в КС-граммати
45. Какая грамматика называется леворекурсивной?
46. Определение множества FIRST1
47. Определение множества FOLLOW1
48. Определение LL(1) Грамматики
49. Определение LR(1) ситуации
50. Определение LR(1) грамматики
51. Какого типа конфликты могут появиться в канонической системе множеств LR(1) ситуаций?
52. Определение конфигурации LR-анализатора
53. Как меняется конфигурация LR-анализатора при действии reduce?
54. Какие типы действий выполняет LR-анализатор?
55. Как меняется конфигурация LR-анализатора при действии shift?
56. Что такое основа правой сентенциальной формы