Pytania otagowane jako word-combinatorics

1
Czy każdy wystarczająco duży ciąg ma powtórzenia?
Niech będzie skończonym zestawem znaków o ustalonym rozmiarze. Niech będzie ciągiem znaków nad . Mówimy, że niepusty substrat z jest powtórzeniem, jeśli dla jakiegoś ciągu .α Σ β αΣΣ\Sigmaαα\alphaΣΣ\Sigmaββ\betaαα\alphaγβ= γγβ=γγ\beta = \gamma \gammaγγ\gamma Teraz moje pytanie dotyczy tego, czy: Dla każdego istnieje pewna liczba taka, że ​​dla każdego łańcucha powyżej …
3
Liczba słów w zwykłym języku
Według Wikipedii , dla każdego zwykłego języka istnieją stałe i wielomiany takie, że dla każdego liczby słów o długości w spełnia równanieLLLλ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)nnnLLL sL(n)=p1(n)λn1+⋯+pk(n)λnksL(n)=p1(n)λ1n+⋯+pk(n)λkn\qquad \displaystyle s_L(n)=p_1(n)\lambda_1^n+\dots+p_k(n)\lambda_k^n . Język L={02n∣n∈N}L={02n∣n∈N}L =\{ 0^{2n} \mid n \in\mathbb{N} \} jest zwykły ( (00)∗(00)∗(00)^* pasuje do niego). sL(n)=1sL(n)=1s_L(n) = 1 iff n jest parzyste, a sL(n)=0sL(n)=0s_L(n) …
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
Faktoryzacji słowo w Czas
Biorąc pod uwagę dwa ciągi , piszemy dla ich konkatenacji. Biorąc pod uwagę ciąg i liczba całkowita , napisać dla złączonych kopii . Teraz biorąc pod uwagę ciąg, możemy użyć tego zapisu do „skompresowania” go, tzn. można zapisać jako . Nazwijmy ten ciężar kompresji liczba znaków w niej występujących, więc …
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.