Pytania otagowane jako regular-language

Pytania o języki formalne, które można opisać wyrażeniami regularnymi (w sensie Kleene) lub, równoważnie, języki, które mogą być akceptowane przez automaty skończone.

1
Czy jest rozstrzygalne, czy długość wyjściowa przetwornika jest ograniczona długością wejściową?
Rozważane tutaj przetworniki to te, które Wikipedia nazywa przetwornikami skończonymi . Zachowanie przetwornika , czyli relacja, którą oblicza, jest zapisywane : słowo jest wyjściem dla iff .[ T ] y x x [ T ] yT.TT[ T][T][T]yyyxxxx [ T] yx[T]yx[T]y Pytanie: Czy można rozstrzygnąć następujący problem: Biorąc pod uwagę: Przetwornik …
1
Uogólnienie stwierdzenia, że ​​monoid rozpoznaje język iff monoid syntaktyczny dzieli monoid
Pozwolić AAAbyć skończonym alfabetem. Dla danego języka składniowym monoid jest dobrze znanym pojęciem w teorii język form. Co więcej, monoid rozpoznaje język jeśli istnieje morfizm taki, że .L⊆A∗L⊆A∗L \subseteq A^{\ast} M(L)M(L)M(L)MMMLLLφ:A∗→Mφ:A∗→M\varphi : A^{\ast} \to ML=φ−1(φ(L)))L=φ−1(φ(L)))L = \varphi^{-1}(\varphi(L))) Mamy więc ładny wynik: Monoid rozpoznaje jeśli jest homomorficznym obrazem submonoidu (napisanego jako …
1
Przejście do członkostwa monoidów w DFA
Biorąc pod uwagę pełne DFA A=(Q,Γ,δ,F)A=(Q,Γ,δ,F)A=(Q, \Gamma, \delta, F), możemy zdefiniować zbiór funkcji fafaf_a dla każdego a∈Γa∈Γa\in \Gammai z fa:Q→Qfa:Q→Qf_a:Q\rightarrow Q, fa(q)=δ(q,a)fa(q)=δ(q,a)f_a(q)=\delta(q, a). Możemy uogólnić to pojęcie na słowow=a1,⋯,amw=a1,⋯,amw=a_1, \cdots, a_m i fw=fa1∘⋯∘famfw=fa1∘⋯∘famf_w=f_{a_1}\circ \cdots \circ f_{a_m} gdzie ∘∘\circoznacza skład funkcji. Ponadto oznaczamyG={fw∣w∈Γ∗}G={fw∣w∈Γ∗}G=\{f_w\mid w\in \Gamma^*\} i GGG jest monoidem. [GGGjest zwykle …
1
Zwykłe języki i stała złożoność komunikacji
Pozwolić L⊆A∗L⊆A∗L \subseteq A^* być językiem i zdefiniować fL:A∗×A∗→{0,1}fL:A∗×A∗→{0,1}f_L\colon A^* \times A^* \to \{0, 1\} przez fL(x,y)=1fL(x,y)=1f_L(x, y) = 1 iff x⋅y∈Lx⋅y∈Lx\cdot y \in L. Szukam referencji dla: Propozycja. LLL jest regularna w deterministycznej złożoności komunikacji fLfLf_L jest stały. Innymi słowy, LLL jest normalny iff istnieje protokół dla dwóch graczy …
1
Czy niedeterministyczne liniowe automaty z ograniczoną liczbą odwiedzin rozpoznają tylko zwykłe języki?
Czy niedeterministyczne liniowe automaty z ograniczoną liczbą odwiedzin rozpoznają tylko zwykłe języki? Przez niedeterministyczny automat związany liniowo (nLBA) mam na myśli niedeterministyczną maszynę Turinga z pojedynczą taśmą, w której dane wejściowe są „wyściełane” znakami końcowymi na obu końcach, których nigdy nie można nadpisać, a więc głowa nigdy nie może wyjść …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.