Apakah pembalikan DFA minimal juga minimal?

Pertanyaannya cukup banyak pada judulnya. Apakah pernah ada waktu di mana beberapa bahasa dapat diterima oleh DFA minimal dengan negara, tetapi , pembalikan , dapat diterima oleh DFA dengan negara, di mana ? $L$ $n$ $L^R$ $L$ $m$ $m<n$

formal-languages reference-request automata finite-automata Ya ampun
sumber

Kebalikan dari DFA bahkan tidak selalu bersifat deterministik. DFA yang menerima regex AAA + memiliki status terminal dengan dua panah masuk dengan label yang sama.

Ian

Jawaban:

L. = (0 + 1)^{2} 2 + (0 + 2)^{2} 1 + (1 + 2)^{2} 0.

$L = (0+1)^22+(0+2)^21+(1+2)^20.$

ϵ, 0, 1, 2, 00, 01, 02, 11, 12, 22, 000, 001

$\epsilon,0,1,2,00,01,02,11,12,22,000,001$

L

$L$

{L.}^{R} = 2 (0 + 1)^{2} + 1 (0 + 2)^{2} + 0 (1 + 2)^{2}

$L^R = 2(0+1)^2 + 1(0+2)^2 + 0(1+2)^2$

0, 1, 2

$0,1,2$

0 (1 + 2), 1 (0 + 2), 2 (0 + 1)

$0(1+2),1(0+2),2(0+1)$

ϵ, 0, 1, 2, 01, 12, 20, 011, 000

$\epsilon,0,1,2,01,12,20,011,000$

$L$ $L^R$

Yuval Filmus
sumber

Terima kasih! Saya entah bagaimana mendapatkannya di kepala saya bahwa Anda bisa membalikkan DFA dan (langsung) mendapatkan DFA kembali, saya pikir saya bingung dengan komplemen.

jmite

@iteite saya memiliki kentut otak yang sama, dan mengetikkan bukti elegan dengan kontradiksi dari jawaban yang salah. :) Ini komplemen yang berfungsi seperti yang saya pikir, bukan pembalikan. Ups.

Patrick87