Пусть регулярный язык задан своим описанием

1. 
   №1 Пусть регулярный язык задан своим описанием:
   
2. 
   Множество всех цепочек из {0,1,a}*, заканчивающихся цепочкой ’a1’ и содержащих чётное количество нулей. Например, ‘a1’, ‘00a1’, ‘010a1’ и т.п.
   
3. 
   Построить регулярное выражение, задающее этот язык.
   
4. 
   
   
5. 
   Решение:
   

1. 
   Последовательность из четного количества нулей и произвольного количества единиц и символов «a»: ((1+a)^*0(1+a)^*0(1+a)^*). Так как данная последовательность может быть повторена произвольное количество раз, добавим соответствующий оператор: ((1+a)^*0(1+a)^*0(1+a)^*)^*.
   
2. 
   Конечные «a» и единица: a1.
   

6. 
   ((1+a)^*0(1+a)^*0(1+a)^*)^*a1
   

№3 Построить КС-грамматику, задающую язык из задачи №1. Сгенерировать две цепочки языка по построенной грамматике. Процесс генерации цепочек языка записать в виде цепочки вывода, указывая номера применённых правил (или сами правила, как показано в примере). Использовать левосторонний или правосторонний вывод.

7. 
   Решение:
   
8. 
   Регулярное выражение имело вид ((1+a)^*0(1+a)^*0(1+a)^*)^*a1. Обозначим A(1+a)^*, B((1+a)^*0(1+a)^*0(1+a)^*)^*. Тогда первое правило будет иметь вид: SBa1. В правиле для B будут присутствовать A: BA0A0A, надо добавить рекурсию и пустое правило: BA0A0AB|. Нетерминал A рекурсивно порождает любые символы кроме ‘0’: A1A|aA|. Итак, рамматика построена, выпишем её полностью.
   
9. 
   G({0,1,a},{S,A,B},P,S), где P:
   
10. 
    SBa1,
    
11. 
    A1A|aA|,
    
12. 
    BA0A0AB|.
    
13. 
    Аналогично №1.
    
14. 
    Эта грамматика более наглядна, чем регулярная.
    
15. 
    Ещё в этом же задании требовалось сгенерировать цепочки языка по полученной грамматике. Покажем на примере одной цепочки, подчёркивая каждый раз нетерминал, который будем раскрывать, и используя правосторонний вывод (каждый раз заменяем крайний правый нетерминал в цепочке вывода).
    
16. 
    S  (правило SBa1) Ba1  (правило BA0A0AB) A0A0ABa1  (правило A) 0A0ABa1  (правило A1A)  0A10ABa1  (правило A) 010ABa1  (правило A) 010Ba1  (правило B) 010a1.
    
17. 
    Выделено неверное применение правила.
    
18. 
    Получили цепочку, соответствующую требованиям языка.
    

19. 
    
    
20. 
    Решение:
    
21. 
    При построении ДКА полезно следовать трём правилам:
    
22. 
    1) Если распознаваемый язык допускает пустую цепочку, то начальное состояние автомата является также и конечным.
    
23. 
    2) Минимальная непустая цепочка языка должна переводить автомат из начального состояния в конечное.
    
24. 
    3) Если все цепочки языка должны иметь длину заданной кратности, то в функции переходов количество состояний в цикле равно этой кратности (и не может быть меньшим!!!). Тогда для цепочек произвольной длины на вершинах графа функции переходов допустимы петли, для чётной длины циклы включают по два состояния, и т.д.
    
25. 
    
    
26. 
    Для наглядности построение функции переходов ДКА будем выполнять сначала в виде графа:
    
27. 
    
    

28. 
    Выпишем полностью построенный ДКА: M({q₀,q₁,q₂,q₃},{0,1,a},,q₀,{q₂})
    
29. 
    Осталось согласно заданию представить функцию переходов ещё и в виде таблицы, а также проверить по автомату построенные в предыдущей задаче цепочку.
    
30. 
    
    

    	вход
    состояние	0	1	а
    q0	{q3}	{q0}	{q1}
    q1	{q3}	{q2}	{q1}
    q2	{q0}	{q0}	{q1}
    q3	{q0}	{q3}	{q3}

31. 
    
    
32. 
    Для наглядности закрасим ячейки таблицы, соответствующие переходам минимальной допустимой цепочки. Рассмотрим разбор построенной в задаче 3 цепочки:
    
33. 
    
    
34. 
    (q0,010a1) ├─ (q3,10a1) ├─ (q3,0a1) ├─ (q0,a1) ├─ (q1,1) ├─ (q2,). Поскольку q2F, это означает, что ‘010a1’L(M).
    
35. 
    №6 Построить детерминированный автомат с магазинной памятью, распознающий язык из задачи №5 и работающий с опустошением стека. Проверить с помощью этого ДМПА допустимость цепочек языка, полученных в задаче №5. Процесс проверки выписать в виде последовательности конфигураций построенного ДМПА, указывая номера правил.
    

При построении функции переходов ДМПА потребуется учитывать несколько факторов – равенство и чётность количества символов ‘a’ и ‘b’, количество символов ‘c’, равное половине количества пар ‘ab’.

Таким образом, определим несколько состояний q₀, q₁, q₂, q₃:

q₀ – прочитан только первый символ ‘a’;

q₁ – прочитана одна пара ‘ab’;

q₂ – прочитано две пары ‘ab’;

q₃ – считан символ ‘с’.

Итак, функция переходов  будет иметь вид:

Осталось выписать полностью ДМПА P и проверить допустимость полученной в предыдущей задаче цепочки, для примера возьмём ‘ababababcc’.

P({q₀,q₁,q₂,q₃},{a,b,c},{Z,a},,q₀,Z,{q₃});

(q₀,ababababcc,Z) ├─ (q₀,babababcc,aZ) ├─ (q₁,abababcc,Z) ├─ (q₁,bababcc,aZ) ├─ (q₂,ababcc,aZ) ├─(q₂,babcc,aaZ) ├─ (q₁,abcc,aZ) ├─ (q₁,bcc,aaZ) ├─ (q₂,cc,aaZ) ├─ (q₃,c,aZ) ├─ (q₃,,Z) ├─ (q₃,,).