Разлика између НФА и ДФА

НФА вс ДФА

Теорија рачунања је грана рачунарске науке која се бави начином на који се проблеми решавају помоћу алгоритама. Има три гране, наиме; теорија сложености рачунања, теорија рачунања и теорија аутомата.

Теорија аутомата или аутомата је проучавање апстрактних математичких машина или система које се могу користити за решавање рачунарских проблема. Аутомат се састоји од стања и прелаза, а како види симбол или слово уноса, он прелази у друго стање узимајући тренутно стање и симбол као улаз.

Теорија аутомата или аутомата има неколико класа које укључују детерминиране коначне аутомете (ДФА) и недетерминистративне коначне аутомете (НФА). Ове две класе су функције транзиције аутомата или аутомата.

У транзицији, ДФА не може користити н празан низ, а може се схватити као једна машина. Ако се низ заврши у стању које није прихватљиво стање, ДФА ће га одбити. ДФА машина се може конструисати са сваким улазом и излазом.

ДФА има само једну транзицију стања за сваки симбол абецеде, а постоји само једно крајње стање за његов прелазак, што значи да за сваки лик који се чита, постоји једно одговарајуће стање у ДФА. Лакше је проверити чланство у ДФА-и, али је теже конструисати. Повратно праћење је дозвољено у ДФА и захтева више простора од НФА.

Повлачење уназад није увек дозвољено у НФА. Иако је у неким случајевима могуће, у другим није. Лакше је конструисати НФА, а захтева и мање простора, али није могуће конструисати НФА машину за сваки улаз и излаз.

Подразумева се као неколико ситних машина које рачунају истовремено, а чланство може бити теже проверити. Користи транзицију празног низа и постоје бројне могуће сљедеће државе за сваки пар стања и симбола уноса. Она започиње у одређеном стању и чита симболе, а аутомат затим одређује следеће стање које зависи од тренутног уноса и других последичних догађаја. У свом стању прихватања, НФА прихвата стринг и одбацује га на други начин.

Резиме:

1. "ДФА" означава "Детерминистичке коначне аутомете", док "НФА" означава "Недодељени коначни аутомати".
2.Бок су функције транзиције аутомата. У ДФА је следеће могуће стање јасно постављено, док у НФА сваки пар стања и симбол уноса могу имати више могућих следећих стања.
3.НФА може користити прелаз празног низа док ДФА не може користити прелаз празни низ.
4.НФА је лакше конструисати, док је ДФА теже конструисати.
5.Бацктрацкинг је дозвољено у ДФА-у док је у НФА-у то може или није дозвољено.
6.ДФА захтијева више простора док НФА захтијева мање простора.
7. Док се ДФА може разумети као једна машина и ДФА машина се може конструисати за сваки улаз и излаз; 8.НФА се може разумети као неколико малих машина које се међусобно рачунају и не постоји могућност конструкције НФА машине за сваки улаз и излаз.