Задания для контрольной работы

Задание 1: Дана грамматика G = {T, N, P, S}. Построить вывод заданной цепочки .

Варианты 1,3,5,7,9. T ={a, b, +, -, *}; N = {S, T, F}; P = {1. S  T; 2. S  T+S; 3. S  T-S; 4. T  F; 5. T  F*T; 6. F  a; 7. F  b}; ;  = a-b*a+b.

Вариант 2,4,6,8,10. T ={a, b, с}; N = {S, B, C}; P = {1. S  aSBC; 2. S  abC; 3. CB  BC; 4. bB  bb; 5. bC  bc; 6. cC  cc }; ;  = aaabbbccc.

Задание 2: К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка?

Вариант 1. T ={a, b, +, -}; N = {S , A , B}; P = {1. S  ABA; 2. B  +; 3. B  -; 4. A    a; 5. A  b}; .

Вариант 2. T ={a, b, c}; N = {S ,Q}; P = {1. S  aQb; 2. S  ; 3. Q    cSc}; .

Вариант 3. T ={0,1}; N = {S ,B}; P = {1. S  1B; 2. B  B0; 3. B    1}; .

Вариант 4. T ={a, b}; N = {S , A , B}; P = {1. S  A; 2. S  SA; 3. S  SB; 4. A    a; 5. B  b}; .

Вариант 5. T ={a, b}; N = {S , B}; P = {1. S  a; 2. S  Ba; 3. B  Bb; 4. B  b}; .

Вариант 6. T ={a, b}; N = {S , A}; P = {1. S  Ab; 2. A  Aa; 3. A  ba}; .

Вариант 7. T ={0,1}; N = {S ,A}; P = {1. S  0A1; 2. S  01; 3. 0A  00A1; 4. A   01}; .

Вариант 8. T ={a, b}; N = {S , A, B}; P = {1. S  AB; 2. AB  BA; 3. A  a; 4. B  b}; .

Вариант 9. T ={a, b}; N = {S , A, B}; P = {1. S  A; 2. S  B; 3. A  aAb; 4. A   0; 5. B  aBbb; 6. B   1}; .

Вариант 10. T ={a, b}; N = {S , A}; P = {1. S  SS; 2. S  A; 3. A  a; 4. A  bb }; .

Задание 3: Построить грамматику, порождающую язык L.

Вариант 1. L = { aⁿ b^m | n=3 m = 1}

Вариант 2. L = { cc | =aa =bb}

Вариант 3. L = { a₁ a₂ ... a_n a_n ... a₂ a₁ | a₁ = 0, a₂ = 1, a₃ = 0 , n = 3}

Вариант 4. L = { aⁿ b^m | n= m =4}

Вариант 5. L = { цепочки из 0 и 1 с неравным числом 0 и 1| 0 больше, чем 1}

Вариант 6. L = { aⁿ b^m | n=1, m=2}

Вариант 7. L = { cc | =ab, =ba }

Вариант 8. L = { a₁ a₂ ... a_n a_n ... a₂ a₁ | a_1,3 = 1, a_2,4 = 0, n = 4}

Вариант 9. L = { aⁿ b^m | n =2, m = 4}

Вариант 10. L = { цепочки из 0 и 1 с неравным числом 0 и 1| 1 больше, чем 0}

Задание 4. Требуется построить конечный автомат, распознающий язык L в алфавите A={a, b,c}, если язык L задается следующим условием: слово принадлежит языку L тогда и только тогда, ...

Вариант 1: когда буква a встречается в слове ровно один раз, а буквы b,c не менее двух раз.

Вариант 2: когда в этом слове не встречается более двух букв а подряд.

Вариант 3: когда в слове сочетание ab встречается не более двух раз.

Вариант 4: когда в слове содержится подслово bbсс.

Вариант 5: когда слово содержит одинаковое число букв a и b.

Вариант 6: когда слово содержит четное число букв.

Вариант 7: когда слово содержит нечетное число букв а.

Вариант 8: когда при наличии в слове буквы a там встречается также и буква b.

Вариант 9: когда каждая буква алфавита встречается в слове не более двух раз.

Вариант 10: когда буквы b, c встречаются в слове ровно один раз,а буква a не менее

двух раз.

25