ом мінімального автомата, але необхідну для закінчення роботи машини Тьюринга з допускає результатом.
9. Опис контрольного прикладу
Призначення
Контрольний приклад необхідний для тестування програмної реалізації автомата - програми В«turingВ».
Вихідні дані
Вхідна ланцюжок символів автомата. Ланцюжки символів складаються з символів вхідного алфавіту автомата: {x0, x1, x2, x3, x4, x5, x6, x7}. p align="justify"> Побудуємо ланцюжка символів, для контрольного прикладу, виходячи з праволінейной граматики. Для перевірки правильності роботи автомата потрібно перевірити його за допомогою допустимих ланцюжків. Що б отримати допустиму ланцюжок символів необхідно взяти одне з правил, в лівій частині якого стоїть початковий сімволS. Виписати всі термінальні символи з цього правила і якщо в кінці стоїть нетермінал, то перейти до одного з правил, в лівій частині якого стоїть цей нетермінал. Виписати термінальні символи з цього правила і якщо в кінці стоїть нетеріманл, то перейти до нового правила і т.д., поки ми не дійдемо до правила, права частина якого закінчується терміналом. p align="justify"> Отже, отримуємо допускають ланцюжка:
1) S -> x5x5x4B -> x4 - допустити
8 лютого
звідси отримуємо ланцюжок: x5x5x4x4;
2) S -> x3C -> x7E -> x5-допустити
3 14 вересня
ланцюжок: x3 x7 x5;
3) S -> x1F -> x3x0x6 - допустити
17 квітня
ланцюжок: x1x3x0 x6;
Для повної перевірки автомата отримаємо кілька неприпустимих ланцюжків. Їх можна отримати, якщо виписувати термінали, не доходячи до терміналу, який стоїть останнім у правилі. Або ж якщо записати термінал, якого нету в правій частині жодного з правил, в лівій частині яких стоїть необхідний нетермінал. p align="justify"> Неприпустимі ланцюжка:
4) x5 x5 x4
5) x3 x7
) x1 x3 x0
Результати випробування програми
Результати випробування програми представлені в таблиці 6.
Таблиця 6. Результат випробування програми
Номер тестованої цепочкіВходная цепочкаРезультат роботи программи1x5 x5 x4 x4цепочка допущена2x3 x7 x5цепочка допущена3x1 x3 x0 x6цепочка допущена6x5 x5 x4цепочка отвергнута7x3 x7цепочка отвергнута8x1 x3 x0цепочка відкинута
Результати випробування програми збіглися з очікуваними, що говорить про правильність побудови мінімального автомата ...
