Bisakah kita mengatakan DFA lebih efisien daripada NFA?

Saya baru saja mulai membaca tentang teori perhitungan. Jika kita membandingkan mana yang lebih kuat (dalam menerima string), keduanya sama. Tetapi bagaimana dengan efisiensi? DFA akan lebih cepat dibandingkan dengan NFA, karena hanya memiliki satu tepi keluar & tidak akan ada ambiguitas. Tetapi dalam kasus NFA kita harus memeriksa semua kasus yang mungkin & itu pasti membutuhkan waktu. Jadi bisakah kita mengatakan DFA lebih efisien daripada NFA?

Tapi, bagian otak saya yang lain juga berpikir bahwa NFA hanya ada dalam teori, jadi kita tidak bisa membandingkan efisiensinya dengan DFA.

Ada dua jawaban, tergantung pada bagaimana Anda mendefinisikan efisien.

Kekompakan representasi

Memberitahu lebih banyak dengan lebih sedikit : NFA lebih efisien.

Mengubah DFA ke NFA adalah mudah dan tidak meningkatkan ukuran representasi.

Namun, ada bahasa reguler yang DFA terkecil secara eksponensial lebih besar daripada NFA terkecil. Contoh tipikal adalah untuk k diperbaiki.$(a|b)^*b(a|b)^k$$k$

Komputasi

Menjalankannya dengan cepat : DFA lebih efisien.

Komputer yang kita gunakan saat ini bersifat deterministik. Itu membuat mereka buruk dalam berurusan dengan non-determinisme. Ada dua cara umum untuk berurusan secara deterministik dengan NFA: mundur di satu sisi, yang agak mahal, atau melacak keadaan aktif, yang berarti setiap transisi akan memakan waktu hingga kali lebih lama (di mana N adalah ukuran NFA) .$N$$N$

$n$$2^n$

Pencocokan DFA adalah linier dalam ukuran string input. Pencocokan NFA melibatkan backtracking sehingga NFA melakukan lebih banyak pekerjaan. Dengan demikian, DFA lebih efisien.

Hanya menambahkan jawaban di atas:

NFA dapat secara komputasi lebih efisien daripada DFA, dalam arti bahwa mereka dapat disimulasikan pada prosesor paralel.

BTW: Saya melihat orang-orang mengatakan bahwa NFA tidak bisa ada dalam kenyataan. Saya mohon untuk berbeda. Komputer dengan sejumlah besar prosesor dapat menjalankan banyak tugas secara paralel dan dapat dianggap sebagai mesin non-deterministik. Satu dapat menetapkan masing-masing cabang perhitungan ke prosesor baru dan menghentikan mereka semua setiap kali salah satu dari mereka menerima.

Jika Anda menggunakan ukuran "jumlah langkah untuk menerima / menolak" murni teoritis , DFA akan selalu lebih murah daripada NFA yang menggunakan$\epsilon$

Seperti yang telah dicatat orang lain, Anda harus mendefinisikan apa arti "efisiensi". Untuk menggambarkan hal ini, saya memberikan model yang masuk akal dengan jawaban yang berbeda.

Mencari hanya pada model otomat (s), yang mengabaikan khususnya bagaimana Anda akan mengimplementasikannya pada mesin nyata, ukuran efisiensi yang jelas adalah "jumlah transisi yang diambil pada menjalankan penerimaan (terpendek)".

$\varepsilon$

Secara teknis berbicara NFA adalah konsep yang lebih umum daripada DFA, karena tidak diperlukan untuk menggunakan nondeterminisme. Dengan kata lain: setiap DFA adalah NFA. Dari perspektif ini ada untuk setiap bahasa sebuah NFA yang setidaknya seefisien DFA paling efisien, untuk ukuran efisiensi apa pun yang Anda sukai.

Selain itu saya setuju dengan Raphael bahwa itu sangat tergantung pada apa yang Anda maksud dengan efisiensi dan implementasi.

Seperti yang kita ketahui tentang Automata yaitu mesin yang dapat melakukan tindakan apa pun tanpa tenaga manusia atau tanpa partisipasi langsung manusia. misalnya: mesin cuci. Finite Automata berarti kita tahu tugas melakukan tugas dengan mesin seperti 1 tekan ON 2 tekan OFF sehingga hanya ada 2 negara yaitu disebut automata terbatas. Sekarang datang ke DFA yaitu Finite automata deterministik. secara formal berarti kita dapat dengan mudah menentukan keadaan tidak ada ambiguitas dan secara informal hanya perlu 1 transisi yang diizinkan pada 1 simbol. NFA: automata terbatas non deterministik. ada perlu lebih banyak waktu untuk menghitung keadaan aktual dan ada ambiguitas dan secara informal mengatakan ada beberapa transisi yang diizinkan pada 1 simbol. dalam hal waktu untuk mencapai tujuan, NFA membutuhkan lebih banyak waktu daripada DFA tetapi NFA dapat memuat lebih banyak data daripada DFA. * DFA dan NFA memiliki kekuatan yang sama untuk mengenali string. terima kasih .. Deepali kaushik