Напишете всички думи (включително и несъществуващи в езика), които се разпознават от крайния автомат.
Отговор:
С преходи 0→1→2→3→крайно състояние: изпонавържа, изпонажелая, изпонапиша, изпонасмея, изпонабера, изпонаискам, изпонападам, изпонапия
С преходи 0→2→3→крайно състояние: понавържа, понажелая, понапиша, понасмея, понабера, понаискам, понападам, понапия
С преходи 0→3→крайно състояние: повържа, пожелая, попиша, посмея, побера, поискам, попадам, попия
Кои преходи от 3 до краен възел трябва да отстраните, за да се гарантира, че графът няма да разпознава несъществуващи глаголи?
Отговор:
3→4 (*повържа)
3→5 (*понажелая, *изпонажелая)
3→7 (*понасмея, *изпонасмея)
3→9 (*понаискам, *изпонаискам)
С премахването на преход 3→4 отстраняваме несъществуващия глагол повържа, но наред с това отстраняваме и съществуващия глагол понавържа. Помислете как може да се преначертае графът, за да се разпознават точно всички съществуващи глаголи без несъществуващи.
Възможно решение:
Разделяме пътищата през графа на:
- 0→1→2→3a: път за образуване на глаголи с из-по-на-;
- 0→1a→3b: път за образуване на глаголи с по-на-;
- 0→3c: път за образуване на глаголи с по-.
Всеки път се продължава към съответно крайно състояние, свързано със съставна част, с която по този път се образува съществуващ глагол. Например, с -вържа имаме преходи 3a→4 (изпонавържа) и 3b→4 (понавържа), но не и 3c→4 (*повържа.)
Продължете сами построяването на графа или намерете друго възможно решение.
