Automata teorisinde NFA( Nondeterministic Finite Automaton ) ve DFA( Deterministic Finite Automaton ) iki Finite State Machine’dir. NFA’da herhangi bir state’de ve gelen bir karakterden birkaç farklı state’e geçiş yapılabilir. Fakat bu DFA’da gelen karaktere göre unic olarak tanımlanır. DFA’ya gelen herbir karakter için yalnızca bir state’e geçiş yapılır. Bu her iki tip automata tipi regular diller üzerinde tanımlanır.
Aşağıda her iki automata için C++ dilinde yazılmış birer örnek verilmektedir. Örnekte, girilen bir string içerisinde “kalem” ve “leman” kelimelerini arayan, bu kelimeleri ararken de her karakter geldiğinde bulunulan stateleri yazdıran bir console uygulaması bulunmaktadır.
“kalem” ve “leman” kelimelerini arayan DFA örneği…
“kalem” ve “leman” kelimelerini arayan NFA örneği…
Hiç yorum yok:
Yorum Gönder