Pytania otagowane jako regular-languages

Pytania dotyczące właściwości klasy zwykłych języków i poszczególnych języków.

2
Kiedy połączenie dwóch regularnych języków jest jednoznaczne?
Biorąc pod uwagę języki i , powiedzmy, że ich konkatenacja jest jednoznaczna, jeśli dla wszystkich słów istnieje dokładnie jeden rozkład z i , a niejednoznaczny inaczej. (Nie wiem, czy istnieje ustalony termin dla tej właściwości - trudna rzecz do wyszukania!) Jako trywialny przykład konkatenacja z samym sobą jest niejednoznaczna ( …
3
Język nieskończony a język skończony
Nie jestem pewien, czy w teorii komputerowej używa się zwrotów „nieskończony” język lub „skończony” język. Myślę, że źródłem problemu jest to, że język taki jak jest nieskończony w tym sensie, że może wygenerować nieskończoną (ale policzalną) liczbę łańcuchów. Jednak nadal może być rozpoznany przez automat skończony .L = { a …
1
Wykładniczy podział między NFA i DFA w obecności związków
Ostatnio zadano interesujące pytanie, a następnie usunięto. W przypadku zwykłego języka jego złożoność DFA jest wielkością minimalnej akceptacji DFA, a złożoność NFA jest wielkością minimalnej akceptacji NFA. Dobrze wiadomo, że istnieje wykładnicza separacja między tymi dwoma złożonościami, przynajmniej wtedy, gdy wielkość alfabetu jest nieograniczona. W istocie, pod język nad alfabetu …
2
Liczba słów o określonej długości w zwykłym języku
Czy istnieje algebraiczna charakterystyka liczby słów o danej długości w zwykłym języku? Wikipedia podaje wynik nieco nieprecyzyjnie: Dla każdego języka regularnego istnieje stałych i wielomiany tak, że dla każdego numer z słowa o długości w spełnia równanie .LLLλ1,…,λkλ1,…,λk\lambda_1,\,\ldots,\,\lambda_kp1(x),…,pk(x)p1(x),…,pk(x)p_1(x),\,\ldots,\,p_k(x)nnnsL(n)sL(n)s_L(n)nnnLLLsL(n)=p1(n)λn1+⋯+pk(n)λnksL(n)=p1(n)λ1n+⋯+pk(n)λkns_L(n)=p_1(n)\lambda_1^n+\dotsb+p_k(n)\lambda_k^n Nie jest określone, w jakiej przestrzeni żyje ( , jak przypuszczam) i …
2
Czy język jednoargumentowy jest regularny, jeśli wykładnikiem jest funkcja liniowa?
Wykonując bieżące zadanie dla moich kursów języków formalnych i automatów, w pewnym sensie utknąłem na ćwiczeniach obejmujących języki jednoargumentowe (mam nadzieję, że to właściwy termin), tj. Języki oparte na jednej literze. Nie chcę jednak pytać o konkretne ćwiczenia, ale raczej o bardziej ogólną hipotezę, którą wymyśliłem: Niech i . Moja …
1
Znalezienie maksymalnej faktoryzacji zwykłych języków
Niech język będzie regularny.L⊆Σ∗L⊆Σ∗\mathcal{L} \subseteq \Sigma^* Rozkład na czynniki to maksymalna para zestawów słów z ( X , Y )LL\mathcal{L}(X,Y)(X,Y)(X,Y) X⋅Y⊆LX⋅Y⊆LX \cdot Y \subseteq \mathcal{L} X≠∅≠YX≠∅≠YX \neq \emptyset \neq Y , gdzie | .x ∈ X , y ∈ Y }X⋅Y={xyX⋅Y={xyX \cdot Y = \{xyx∈X,y∈Y}x∈X,y∈Y}x \in X, y \in Y\} …
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.