Контрольная работа 1
.2.pdfКонтрольная работа №1.2
1По правилам грамматики построить граф конечного автомата.
2По графу конечного автомата определить распознаваемое им регулярное выражение
по следующей схеме.
S -> C c A -> a
| C a B -> b
| C b C -> A b | B a
Fig. 1: The initial state appears due to applying the following productions A a and B b to get the final state H.
Turning the above grammar rules into the following right-linear form: S -> aA, S - > bB, C -> cD, C -> aA, A -> bC, C -> bB, B -> aC, C -> c.
Fig. 2: The initial state appears due to productions A -> a and B -> b.
Fig. 3: Getting the condensed upper graph.
Writing the regular expression
L = (ab+ba)(ab+ba)*c
3К полученному регулярному выражению применить алгоритм № III Мак-Нотона- Ямады-Томпсона.
4Преобразовать НКА, полученный с помощью алгоритма № III, в ДКА, используя алгоритмы I и II, приведенные в описании.
Описание к Контрольной работе №1.2 Индивидуальные задания к Контрольной работе №1.2 прежние