Wir wissen, dass reguläre Ausdrücke (RE) mit endlichen Automaten (FA) implementiert werden. In einigen Sprachen (wie JavaScript) in RE gibt es Funktionen wie "Erfassen von Klammern" mit "Rückreferenzen":
Also habe ich lange versucht, dies zu knacken und habe fast das Gefühl, dass ich mich über diese Frage in Schleifen befinde. Angesichts der folgenden NFA: Verwenden Sie den GNFA-Algorithmus, um den regulären Ausdruck zu erhalten. Ich verstehe, dass Sie für den ersten Schritt (Hinzufügen leerer...
Ich möchte beweisen, dass regulär ist, wenn regulär ist, aber ich komme anscheinend nicht weiter. Wenn möglich, hoffte ich auf einen Hinweis, um mich in die richtige Richtung zu bringen. Danke für deine Hilfe.L−−√={w:ww∈L}L={w:ww∈L}\sqrt{L}=\{w:ww\in L\}LLL Meine Idee, um die Regelmäßigkeit der...
Gegeben als String über einig Alphabet, was ist der beste bekannte Algorithmus einen entsprechenden deterministischen endlichen Automaten (DFA) , die ein beliebige Zeichenfolge akzeptiert zu berechnen, enthält ?ssssss Ich bin hauptsächlich an der geringsten zeitlichen Komplexität interessiert. Wenn...
Angenommen, wir haben 3 DFAs. Wir wissen, wie man sie ODER, UND oder NICHT. Aber wie macht man sie XOR? Es gibt keine einzige Erwähnung online. xX O R.yX O R.z= ( ( x | y) ( ¬ x | y) | z) ( ¬ ( ( x | y) ( ¬ x | y) ) | z)xXORyXORz=((x|y)(¬x|y)|z)(¬((x|y)(¬x|y))|z)x\; \mathrm{XOR} \;y\; \mathrm{XOR}...
Für meine Bachelorarbeit betrachte ich die Klasse von Sprachen, die von symmetrischen DFAs erkannt werden, dh deterministische (vollständige) endliche Automaten, die die folgende Bedingung erfüllen: Sei ein vollständiger DFA über dem Alphabet . Wenn es für jedes a \ in \ Sigma und jeden Übergang u...
Seik∈Nk∈Nk\in \mathbb N Ich suche nach einem kleinen NFA-Build für die Sprache der Verkettung von zwei Wörtern der Länge die unterschiedlich sind, dhkkkLk={u⋅v∈Σ∗:|u|=|v|=k∧∀i,ui≠vi}Lk={u⋅v∈Σ∗:|u|=|v|=k∧∀i,ui≠vi}L_k=\{u\cdot v \in \Sigma^* : |u|=|v|=k\wedge \forall i, u_i\neq v_i\} Beachten Sie,...
Sei der String-Matching-Automat für das Muster , das heißtAP=(Q,Σ,δ,0,{m})AP=(Q,Σ,δ,0,{m})A_P = (Q,\Sigma,\delta,0,\{m\})P∈ΣmP∈ΣmP \in \Sigma^m Q={0,1,…,m}Q={0,1,…,m}Q = \{0,1,\dots,m\} δ(q,a)=σP(P0,q⋅a)δ(q,a)=σP(P0,q⋅a)\delta(q,a) = \sigma_P(P_{0,q}\cdot a) für alle undq∈Qq∈Qq\in Qa∈Σa∈Σa\in...