1. Контрольные вопросы

1. Какие грамматики называются регулярными?

2. Чем отличается детерминированный конечный автомат от недетерминированного?

3. Связь регулярных грамматик и конечных автоматов.

4. Что такое регулярное выражение?

5. Алгоритм получения детерминированного конечного автомата из недетерминированного.

6. Какие программные особенности отмечены при написании синтаксического анализатора.

7. Что такое состояние отказа в автомате, соответствующем анализатору?

8. Что такое грамматика?

10. Варианты заданий.

Вариант задания определяется по последним двум цифрам зачётной книжки.

1. (0110)* (1101)* (0111)*

2. (abaa)* (baba)* (abbb)*

3. (a120)* (a001)* (baa0)*

4. (a1b1)* (11a1)* (b1aa)*

5. (21b)* (112b)* (b122)*

6. (baba)* (abab)* (aaba)*

7. (1011)* (1100)* (0001)*

8. (a1b1)* (b12a)* (bb1)*

9. (bba1)* (11aa)* (1ba1)*

10. (b211)* (1abb)* (b11a)*

11. (ab11)* (a11b)* (1aa1)*

12. (bb12)* (2bb1)* (1b21)*

13. (1000)* (1001)* (0001)*

14. (1ab1)* (2b22)* (ab1b)*

15. (ba21)* (1bba)* (2a11)*

16. (ba22)* (11bb)* (2baa)*

17. (0001)* (1011)* (1000)*

18. (bb2a)* (a2bb)* (12ba)*

19. (1b0a)* (1ab2)* (120a)*

20. (1ab0)* (11ab)* (11a0)*

21. (bba2)* (bb01)* (bb0a)*

22. (bb00)* (a12b)* (baab)*

23. (1100)* (1000)* (1011)*

24. (1abb)* (1aa0)* (1bbb)*

25. (2110)* (1210)* (1101)*

26. (baba)* (cbab)* (abbb)*

27. (1010)* (c010)* (1110)*

28. (01ab)* (ba10)* (a10a)*

29. (a010)* (0010)* (0110)*

30. (ab11)* (11ab)* (a1a1)*

31. (ccaa)* (0caa)* (a0ca)*

32. (a010)* (0011)* (1001)*

33. (1001)* (1aa0)* (0a11)*

34. (10a1)* (0011)* (1100)*

35. (a100)* (01a0)* (11aa)*

36. (a010)* (01a0)* (aa11)*

37. (01a0)* (a011)* (010a)*

38. (10a0)* (1a01)* (110a)*

39. (1b01)* (01b1)* (b1b1)*

40. (1101)* (c010)* (00cc)*

41. (0c10)* (0101)* (1101)*

42. (abca)* (caca)* (baba)*

43. (0001)* (0101)* (0a10)*

44. (00a1)* (a110)* (a10a)*

45. (11a0)* (a01a)* (01a0)*

46. (10a1)* (0a10)* (01a0)*

47. (ca0a)* (caca)* (c0c0)*

48. (01cc)* (cc10)* (c01c)*

49. (01aa)* (1010)* (a00a)*

50. (a00a)* (01a0)* (0a01)*

51. (0aa1)* (a001)* (a0a1)*

52. (0a01)* (10a1)* (0a10)*

53. (10a1)* (0a10)* (a1a1)*

54. (a0a0)* (a001)* (0a1a)*

55. (aa01)* (01aa)* (000a)*

56. (a01a)* (a001)* (00a0)*

57. (0a10)* (a101)* (a001)*

58. (0a10)* (00a1)* (a100)*

59. (1a01)* (a101)* (001a)*

60. (1a01)* (0a10)* (a01a)*

61. (1021)* (2021)* (2010)*

62. (2010)* (2100)* (2220)*

63. (2102)* (2201)* (2202)*

64. (2010)* (0012)* (2001)*

65. (1010)* (2001)* (2220)*

66. (1210)* (0201)* (2202)*

67. (01a0)* (01a1)* (1a01)*

68. (a101)* (a110)* (a10a)*

69. (1202)* (2102)* (2001)*

70. (0012)* (2011)* (1021)*

71. (abab)* (baba)* (bbaa)*

72. (baab)* (abab)* (bbaa)*

73. (a101)* (1a01)* (0a11)*

74. (1a01)* (a10a)* (a101)*

75. (0a10)* (a111)* (aa10)*

76. (a10a)* (a101)* (a1aa)*

77. (aaa0)* (a010)* (011a)*

78. (a010)* (a1a0)* (a100)*

79. (aa11)* (100a)* (0a10)*

80. (10aa)* (a0a1)* (1a10)*

81. (a10a)* (a1a0)* (01a1)*

82. (a10a)* (a1a0)* (00a1)*

83. (a1a0)* (0a01)* (a101)*

84. (1a01)* (a1a0)* (a0a1)*

85. (abac)* (caba)* (baca)*

86. (1010)* (1c01)* (cc10)*

87. (01c0)* (0110)* (c0c0)*

88. (0c01)* (c01c)* (c110)*

89. (1012)* (2100)* (0120)*

90. (1021)* (1210)* (2210)*

91. (1101)* (2010)* (2012)*

92. (2010)* (1021)* (2121)*

93. (caba)* (cabb)* (abac)*

94. (abab)* (abcc)* (ccab)*

95. (caca)* (baba)* (bacc)*

96. (abca)* (abca)* (cbaa)*

97. (0120)* (0012)* (2100)*

98. (abab)* (cbcc)* (baca)*

99. (baca)* (babc)* (cbba)*

100. (babb)* (aacb)* (ccab)*