حل تمرین نظریه زبانها و ماشینها/فصل سوم/حل تمرین بخش ۳-۱/حل تمرین ۲۱

برای حل این مساله یک NFA طراحی می‌کنیم. چون زبان r یک زبان منظم است پس می‌توان برای آن یک NFA طراحی کرد. برای تغییر آن وضعیت شروع را به وضعیت پایان تغییر داده و وضعیت پایان را به وضعیت شروع تغییر می‌دهیم.
برای یال ها هم اینگونه عمل می‌کنیم : تمام یال ها تغییر جهت می‌دهد (یعنی برای هر یک از وضعیت ها که ورودی هستند خروجی می‌شوند و بالعکس. اما عناصر روی آنها را تغییر نمی‌دهیم.آنگاه NFA حاصل زبان مورد نظر را تشخیص می‌دهد.