Основные определения по курсам

«Теория и реализация языков программирования» и

«Формальные языки трансляций»

для успешной сдачи зачёта/ экзамена в 2006/7 учебном году

(примерный список)

1. Определение грамматик типа 0 по Хомскому

2. Определение грамматик типа 1 (неукорачивающих) по Хомскому

3. Определение детерминированной машины Тьюринга

4. Определение недетерминированной машины Тьюринга

5. Определение конфигурации машины Тьюринга

6. Определение языка, допускаемого машиной Тьюринга

7. Соотношение между языками, порождаемыми грамматиками типа 0 и языками, допускаемыми машинами Тьюринга

8. Объяснить разницу между недетерминированной и детерминированной машиной Тьюринга

9. Определение регулярного множества

10. Определение регулярного выражения

11. Определение праволинейной грамматики

12. Определение недетерминированного конечного автомата

13. Определение детерминированного конечного автомата

14. Объяснить разницу между недетерминированным и детерминированным конечным автоматом

15. Определение конфигурации конечного автомата

16. Определение языка, допускаемого конечным автоматом

17. Определение е-замыкания для подмножества состояний НКА

18. Определение расширенной функции переходов для КА

19. Определение функции firstpos для поддерева в дереве регулярного выражения

20. Определение функции lastpos для поддерева в дереве регулярного выражения

21. Определение функции followpos для позиций в дереве регулярного выражения

22. Сформулировать соотношение между регулярными множествами и языками, допускаемыми КА

23. Сформулировать соотношение между регулярными множествами и языками, определяемыми праволинейными грамматиками (ПГ).

24. Определение регулярной грамматики

25. Сформулировать соотношение между языками, порождаемыми праволинейными грамматиками и языками, допускаемыми КА

26. Сформулировать лемму о разрастании для регулярных множеств

27. Определение контекстно-свободной грамматики без е-правил

28. Определение контекстно-свободной грамматики

29. Определение вывода в КС-грамматике

30. Определение языка, порождаемого КС-грамматикой

31. Определение сентенциальной формы

32. Определение однозначной КС-грамматики

33. Определение неоднозначной КС-грамматики

34. Определение недетерминированного МП автомата

35. Определение детерминированного МП автомата

36. Определение конфигурации МП автомата

37. Определение языка, допускаемого МП автоматом

38. Определение недетерминированного МП автомата, допускающего опустошением магазина

39. Соотношение, между языками, порождаемыми КС-грамматиками, и языками, допускаемыми недетерминированными МП автоматами

40. Формулировка леммы о разрастании для КС-языков

41. Определение расширенного МП-автомата

42. Определение нормальной формы Хомского для КС-грамматики

43. Определение правостороннего вывода в КС-грамматике

44. Определение левостороннего вывода в КС-грамматике

45. Определение FIRST_k(u)

46. Определение FOLLOW₁(N)

47. Как устроена таблица LL(1) анализатора?

48. Определение LL(1) грамматики

49. Определение основы правой сентенциальной формы

49. Как устроена таблица LR(1) анализатора?

50. Какие конфликты могут быть в таблице действий, построенной по канонической системе множеств LR(1) ситуаций?

51. Определение LR(1) грамматики.

52. Определение LL(k) грамматики.

53. Определение LR(k) грамматики.

54. Определение атрибутной грамматики

55. Определение наследуемых атрибутов грамматики

56. Определение синтезируемых атрибутов грамматики

57. Опишите сущность синтаксически управляемой трансляции.