Sebuah robot yang terbatas nondeterministic adalah mesin negara yang terbatas di mana tuple dipetakan ke beberapa negara. Yaitu. kita ganti biasa δ : Q × Σ → Q fungsi transisi dari DFA dengan fungsi lain Δ : Q × Σ → P ( Q ) .$(state,symbol)$$\delta : Q \times \Sigma \to Q\ $$\Delta : Q \times \Sigma \to \mathcal{P}(Q)$

Jika Anda tahu apa itu NFA, Anda mungkin ingin melewatkan bagian selanjutnya.

Definisi Resmi

NFA dijelaskan secara unik oleh

• satu set terbatas negara$Q$
• seperangkat simbol yang terbatas$\Sigma$
• fungsi transisi$\Delta : Q \times \Sigma \to \mathcal{P}(Q)$
• keadaan awal$q_0 \in Q$
• seperangkat keadaan akhir$F \subseteq Q$

Mesin dimulai pada dan membaca string simbol hingga w ∈ Σ ∗ , untuk setiap simbol secara simultan akan menerapkan fungsi fungsi transisi dengan status saat ini dan menambahkan setiap set status baru ke set status saat ini.$q_0$$w \in \Sigma^*$

Tantangan

Untuk tantangan ini kita akan mengabaikan untuk menyederhanakan itu, selanjutnya alfabet akan selalu menjadi (huruf kecil) huruf a untuk z dan set negara akan { 0 ... N } untuk beberapa non-negatif bilangan bulat N . Keadaan awal akan selalu 0 .$F\ $$\texttt{a}\ $$\texttt{z}\ $$\{0 \dots N\}$$N$$0$

Diberi kata dan deskripsi NFA, tugas Anda adalah menentukan semua status akhir.$w \in \{\texttt{a}\dots\texttt{z}\}^*$

Contoh

Pertimbangkan string dan deskripsi berikut:$\texttt{abaab}$

state, symbol, new-states
0, 'a', [1]
1, 'a', [0]
1, 'b', [1,2]

Mesin akan mulai pada :$q_0 = 0$

1. baca sebuah : status baru { 1 $\texttt{a}$$\{1\}$
2. membaca : negara-negara baru { 1 , 2 $\texttt{b}$$\{1,2\}$
3. baca : status baru { 0 $\texttt{a}$$\{0\}$
4. baca : status baru { 1 $\texttt{a}$$\{1\}$
5. membaca : negara-negara baru { 1 , 2 $\texttt{b}$$\{1,2\}$

Jadi status akhir dan dengan demikian outputnya adalah .$\{1,2\}$

Catatan: Pada langkah (2) transisi status peta ke ∅ karena deskripsi hanya menyertakan transisi ke set yang tidak kosong.$2$$\emptyset$

Aturan

Input akan terdiri dari string dan semacam deskripsi NFA (tanpa -transisi):$\epsilon$

• string input akan selalu menjadi elemen $\{\texttt{a}\dots\texttt{z}\}^*$
• input yang valid (tidak terbatas pada):
  • daftar / array tupel / daftar
  • input baris baru yang dipisahkan
• deskripsi NFA hanya akan berisi transisi dengan set yang tidak kosong sebagai hasilnya
  • Anda dapat menyingkat aturan dengan karakter yang sama jika hasilnya sama (mis. aturan 0,'a',[1,2]dan 0,'b',[1,2]dapat disingkat0,"ab",[1,2]
  • Anda dapat mengambil setiap aturan secara terpisah (mis. aturan 0,'a',[1,2]dapat 0,'a',[1]dan 0,'a',[2])
• Anda dapat memilih huruf besar jika Anda mau
• Anda dapat mengambil jumlah status sebagai input
• Anda dapat mengasumsikan semacam pemesanan input (mis. dipesan oleh negara atau simbol)

Output akan berupa daftar / set / output baris baru dll. Dari status akhir

• pesanan tidak masalah
• tidak ada duplikat (karena set)

Uji kasus

Contoh-contoh ini akan berada dalam format di description word -> statesmana descriptionada daftar tupel (state,symbol,new-states):

[]  "x" -> []
[]  "" -> [0]
[(0,'a',[1]),(1,'a',[0]),(1,'b',[1,2])]  "abaab" -> [1,2]
[(0,'a',[1]),(1,'a',[0]),(1,'b',[1,2])]  "abc" -> []
[(0,'p',[0,1]),(0,'g',[2]),(1,'c',[1]),(1,'g',[4]),(1,'p',[2]),(2,'c',[0])]  "ppcg" -> [2,4]
[(0,'f',[1]),(1,'o',[1,2]),(2,'b',[3]),(3,'a',[4]),(4,'r',[0,4])]  "foobar" -> [0,4]
[(0,'f',[1]),(1,'o',[1,2]),(2,'b',[3]),(3,'a',[4]),(4,'r',[0,4])]  "fooooooobar" -> [0,4]
[(0,'f',[1]),(1,'o',[1,2]),(2,'b',[3]),(3,'a',[4]),(4,'r',[0,4])]  "fobarfo" -> [1,2]
[(0,'f',[1]),(1,'o',[1,2]),(2,'b',[3]),(3,'a',[4]),(4,'r',[0,4])]  "foobarrf" -> [1]
[(0,'d',[1,2]),(1,'u',[2]),(2,'u',[2,3]),(2,'p',[3]),(3,'p',[3])]  "dup" -> [3]
[(0,'a',[0,2]),(0,'b',[3]),(1,'a',[1]),(1,'b',[1]),(2,'b',[1,4]),(4,'b',[2])]  "aab" -> [3,1,4]
[(0,'a',[0,2]),(0,'b',[3]),(1,'a',[1]),(1,'b',[1]),(2,'b',[1,4]),(4,'b',[2])]  "abb" -> [1,2]

Haskell , 66 byte

import Data.List
f d=foldl(\s c->nub[r|(y,r)<-d,g<-s,(g,c)==y])[0]

Cobalah online!

Brachylog , 42 byte

,0{hẸ&t|∋₁B∋IhJ&tJ&hhC∧I∋₁C∧It∋S&hb;B,S↰}ᵘ

masukan sebagai [string, nfa] di mana nfa adalah daftar transisi status [keadaan awal, huruf, status baru sebagai daftar]

Penjelasan

,0                                              # Append 0 to the input (initial state)
  {                                      }ᵘ     # Find all unique outputs
   h                                            # if first element (string)
    Ẹ                                           #   is empty
     &t                                         #   then: return last element (current state)
       |                                        #   else:
        ∋₁B                                     #       save the state transitions in "B"
           ∋I                                   #       take one of these transitions, save in "I"
             hJ                                 #       take the initial state requirement, store in "J"
               &tJ                              #       make sure "J" is actually the current state
                  &hhC                          #       Save first char of string in C
                      ∧I∋₁C                     #       make sure the char requirement for the state transition is the current char
                           ∧It∋S                #       Make "S" equal to one of the new states
                                &hb             #       Behead the string (remove first char)
                                   ;B,S         #       Add B (the state transitions) and S (the new state)
                                       ↰        #       recur this function

Cobalah online!

Brachylog v2, 31 byte

{b,Ȯ,Ȯ\c↔,0↔ġ₃kH&hg;Hz{∋ᵈ}ᵐtt}ᵘ

Cobalah online! ( atau dengan contoh yang lebih kompleks )

Brachylog sangat bagus dalam masalah semacam ini, dan sangat buruk pada masalah yang membutuhkan dua input dan output terpisah. Hampir semua program ini hanya plumbing.

Format input adalah daftar yang berisi dua elemen: yang pertama adalah daftar transisi keadaan ([oldState, symbol, newState] ), dan yang kedua adalah daftar simbol. Saya awalnya merencanakan program ini untuk bekerja dengan kode karakter untuk simbol (karena penanganan string Brachylog kadang-kadang bisa agak aneh), tetapi ternyata karakter berfungsi juga (walaupun Anda harus menulis string input sebagai daftar karakter, bukan sebagai Sebuah benang). Jika pasangan simbol-negara dapat bertransisi ke beberapa negara yang berbeda, Anda menulis beberapa transisi untuk menghadapinya.

Penjelasan

{b,Ȯ,Ȯ\c↔,0↔ġ₃kH&hg;Hz{∋ᵈ}ᵐtt}ᵘ
{                            }ᵘ   Find all distinct outputs that can result from:
 b                                  taking the input minus its first element,
  ,Ȯ                                appending a singleton list (i.e. an element)
    ,Ȯ                              then appending that same element again
      \                             and transposing;
       c                            then concatenating the resulting lists,
        ↔,0↔                        prepending a 0,
            ġ₃                      grouping into blocks of 3 elements
              k                       (and discarding the last, incomplete, block),
               H&                   storing that while we
                 h                  take the first input element,
                  g  z              pair a copy of it with each element of
                   ;H                 the stored value,
                      {  }ᵐ         assert that for each resulting element
                       ∋ᵈ             its first element contains the second,
                        ᵈ ᵐ           returning the list of second elements,
                            t       then taking the last element of
                           t          the last element.

Mungkin lebih mudah untuk mengikuti ini dengan melihat apa yang dihasilkan sebagian versi program. Menggunakan input berikut setiap kali:

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]

kita dapat mengamati output dari beberapa awalan program ini:

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,Ȯ,Ȯ
[[97,98,97,97,98],L,L]

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,Ȯ,Ȯ\
[[97,A,A],[98,B,B],[97,C,C],[97,D,D],[98,E,E]]

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,Ȯ,Ȯ\c↔,0↔
[0,97,A,A,98,B,B,97,C,C,97,D,D,98,E,E]

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,Ȯ,Ȯ\c↔,0↔ġ₃k
[[0,97,A],[A,98,B],[B,97,C],[C,97,D],[D,98,E]]

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,Ȯ,Ȯ\c↔,0↔ġ₃kH&hg;Hz
[[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[0,97,A]],
 [[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[A,98,B]],
 [[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[B,97,C]],
 [[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[C,97,D]],
 [[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[D,98,E]]]

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,Ȯ,Ȯ\c↔,0↔ġ₃kH&hg;Hz{∋ᵈ}ᵐ
e.g. [[0,97,1],[1,98,1],[1,97,0],[0,97,1],[1,98,1]]

Untuk contoh pertama di sini, Lpada awalnya merupakan elemen yang tidak diketahui, tetapi ketika kami memindahkannya melalui \, Brachylog menyadari bahwa satu-satunya kemungkinan adalah daftar dengan panjang yang sama dengan input. Contoh terakhir di sini adalah nondeterministic; kami memodelkan nondeterminisme di NFA menggunakan nondeterminisme di Brachylog itu sendiri.

Kemungkinan peningkatan

Beberapa sintaks di sini, seperti ↔,0↔dan terutama kekacauan dengan H&hg;Hz{…ᵈ}ᵐ, cukup kikuk. Itu tidak akan mengejutkan saya jika ada cara terserat untuk mengucapkan ini.

{∋ᵈ}ᵐdalam dirinya sendiri struktur yang cukup mencurigakan - Anda hanya berharap bisa menulis ∋ᵈᵐ- tetapi tidak menguraikan karena alasan tertentu.

Python 3, 103 80 byte

terima kasih kepada @BWO

w=lambda n,f,a={0}:w(n,f[1:],{y for(x,c,y)in n if c==f[0]and{x}&a})if''<f else a

TIO

Pemahaman daftar "elegan" (103 byte) sebelumnya:

def w(a,b):
    q=[0]
    for c in b:q=[j for s in q for i in a if s in i if i[1]==c for j in i[2]]
    return q

JavaScript (ES6), 99 byte

Mengambil input sebagai (nfa)(string). Mengembalikan Set.

a=>g=([c,...b],s=[0])=>c?g(b,a.reduce((p,[x,y,z])=>s.includes(x)&y==c?[...p,...z]:p,[])):new Set(s)

Cobalah online!

R , 81 byte

function(a,b,e,s)Reduce(function(A,x)unique(e[a%in%A&b==x]),el(strsplit(s,"")),0)

Cobalah online!

Jawaban langsung menggunakan Reduce. Mengambil aturan sebagai tiga vektor yang state, symbol, new-statesdipanggil a,b,e.

Aturan terpisah (mis. Aturan 0,'a',[1,2]adalah 0,'a',1dan 0,'a',2).

Kelapa , 64 byte

d->reduce$((s,c)->{r for(*y,r)in d for S in s if[S,c]==y},?,{0})

Cobalah online!

Bersih , 68 byte

Yang ini berdasarkan pada solusi Haskell ovs sedikit lebih pendek dari pendekatan awal saya.

sekarang termasuk test harness

import StdEnv
?d=foldl(\s c=removeDup[r\\(y,r)<-d,g<-s|(g,c)==y])[0]

Cobalah online!

Arang , 44 byte

⊞υ⁰Ｆη«≔υζ≔⟦⟧υＦζＦθ¿∧⁼§λ⁰κ⁼§λ¹ιＦ§λ²¿¬№υμ⊞υμ»Ｉυ

Cobalah online! Tautan adalah untuk mengucapkan versi kode. Penjelasan:

⊞υ⁰

Dorong 0ke daftar kosong yang telah ditentukan untuk mengatur status inital$\{0\}$.

Ｆη«

Ulangi input.

≔υζ

Salin negara bagian.

≔⟦⟧υ

Setel ulang status.

Ｆζ

Ulangi salinan negara.

Ｆθ

Ulangi entri NFA.

¿∧⁼§λ⁰κ⁼§λ¹ι

Jika entri cocok, maka ...

Ｆ§λ²

... lewati negara bagian baru ...

¿¬№υμ

.... jika mereka belum ada dalam daftar ...

⊞υμ»

... tambahkan ke daftar.

Ｉυ

Keluarkan daftar status ke string untuk output implisit pada baris terpisah.

Perl 6 , 61 54 byte

->\n,\s{set +s&&reduce {n.grep(*[^2]⊆@_)[*;2]},0,|s}

Cobalah online!

Mengambil daftar transisi keadaan dan string input sebagai daftar karakter.

Japt , 31 byte

W=[W]c;Ê?ßUÅVVf!øW føUg)mÌc):Wâ

Cobalah!

Disimpan 2 byte dengan lebih baik menggunakan kemampuan Japt untuk secara implisit membentuk fungsi dari beberapa input

Penjelasan:

W=[W]c;                            Initialize the state set to [0] on the first run
       Ê?                   :Wâ    If the input is empty return the unique states; else...
             Vf!øW                 Get the transitions valid for one of the current states
                   føUg)           Of those, get the ones valid for the current character
                        mÌc)       Merge the states of the remaining transitions
         ßUÅV                      Repeat with the remaining characters as input

Kode "inisialisasi negara" yang baru dapat menggunakan sedikit lebih banyak detail. Japt menginisialisasi Wke 0 jika ada kurang dari 3 input, jadi jalankan pertama [W]adalah [0], dan c"meratakan" array. [0]sudah serata mungkin, jadi tidak berubah. Pada menjalankan selanjutnya Wmemiliki nilai yang berbeda, misalnya [1,2]. Dalam hal itu [W]menjadi [[1,2]], array elemen tunggal di mana elemen itu adalah array. Kali ini cmembuka bungkusnya dan kembali ke [1,2]. Jadi, pada run pertama itu W=[0]dan pada run berikutnya itu W=W.