Формальные языки

1)Отобразить следующий КА в виде таблицы переходов и в виде графа.

2)Для каждoго КА проверить на проходимость по 5 слова. (3 правильных и 2 неправильных)

3)Построить эквивалентную регулярную грамматику

4)Для двух слов, принятых конечным автоматом, доказать что путем вычисления производных порождение этих слов и регулярной грамматики.

5)Постройте дерево вывода для каждого из сгенерированных слов

6)Для недетерминированных КА построить эквивалентные детерминированные КА.

7)Представьте детерминированный конечный автомат в графической форме.

8)Для двух слов, принятых недетерминированным конечным автоматом, продемонстрируйте с помощью вычисления конфигурации принятие этих слов детерминированным конечным автоматом.

9)Постройте uvw-представление для трех слов, распознаваемых детерминированным конечным автоматом, применив лемму о разрастании(pumping Lemma).

a)AF=(Q,Σ,δ,q0,F), Q={q0,q1,q2,q3}, Σ={a,b,c,d}, F={q3}, δ(q0,d)={q1,q2}, δ(q1,b)={q1,q3}, δ(q1,a)={q2}, δ(q2,b)={q0,q2}, δ(q2,c)={q2}, δ(q3,c)={q3}, δ(q3,b)={q1}

b)AF=(Q,Σ,δ,q0,F), Q={q0,q1,q2,q3}, Σ={9,1,3}, F={q3}, δ(q0,3)={q1}, δ(q0,9)={q1, q0}, δ(q1,3)={q0}, δ(q1,1)={q2}, δ(q2,9)={q1}, δ(q2,3)={q3}, δ(q3,9)={q1}