Właśnie zaczynam wchodzić w teorię obliczeń, która bada, co można obliczyć, jak szybko, z wykorzystaniem ilości pamięci iz jakim modelem obliczeniowym. Mam dość podstawowe pytanie, ale naprawdę mam nadzieję, że niektórzy z was pomogą mi zrozumieć koncepcję: Dlaczego wszystko koncentruje się...
Pytanie jest prawie w tytule. Czy jest jakiś czas, kiedy jakiś językLLL może być zaakceptowany przez minimalną DFA z nnn stwierdza, ale LRLRL^R, odwrócenie LLL, może zostać zaakceptowany przez DFA za pomocą mmm państwa, gdzie
Pracuję z algorytmem dopasowywania wzorców, który generuje acykliczny automat stanów skończonych, który akceptuje dany ciąg tekstowy i wszystkie jego podciągi. Algorytm FSA jest uruchamiany na symbolicznej reprezentacji strumienia muzycznego (np. Dane MIDI). Strumień muzyczny został wstępnie...
Jednym ze sposobów patrzenia na wyrażenia regularne jest konstruktywny dowód na następujący fakt: możliwe jest zbudowanie języków regularnych, zaczynając od małego zestawu języków i łącząc je za pomocą małego, stałego zestawu właściwości zamknięcia. W szczególności, jeśli zaczniemy od pustego...
Wiem, że języki, które można zdefiniować za pomocą wyrażeń regularnych i te rozpoznawane przez DFA / NFA (automaty skończone) są równoważne. Nie istnieje również DFA dla języka . Ale nadal może być napisane przy użyciu wyrażeń regularnych (zresztą każdy non-język regularny może być) jako . Wiemy...
Z mojego czytania wynika, że większość gramatyk dotyczy generowania nieskończonej liczby łańcuchów. Co jeśli pracowałeś na odwrót? Jeśli podano n łańcuchów o długości m, powinno być możliwe stworzenie gramatyki, która wygeneruje te łańcuchy i tylko te łańcuchy. Czy istnieje znana metoda...
Pracuję nad ciężkim ćwiczeniem w podręczniku i po prostu nie mogę wymyślić, jak postępować. Oto problem. Załóżmy, że mamy język gdzie jest liczbą nieracjonalną. Jak mam udowodnić, że nie jest językiem bezkontekstowym?L={aibj:i≤jγ,i≥0,j≥1}L={aibj:i≤jγ,i≥0,j≥1}L = \{a^ib^j: i \leq j \gamma, i\geq 0,...
Zacząłem studiować niedeterministyczne automaty, korzystając z książki Hopcroft i Ullman . Utknąłem w problemie, który uznałem za bardzo interesujący: Daj niedeterministyczny automat skończony akceptujący wszystkie ciągi, które mają tę samą wartość, gdy są oceniane od lewej do prawej, od prawej...
Utknąłem, rozwiązując następne ćwiczenie: Argumentuj, że jeśli L.LL jest bezkontekstowy i RRR jest zatem regularny L / R = { w ∣ ∃ x ∈ Rśww x ∈ L }L/R={w∣∃x∈Rs.twx∈L}L / R = \{ w \mid \exists x \in R \;\text{s.t}\; wx \in L\} (tj. odpowiedni iloraz ) jest pozbawiony kontekstu. Wiem, że powinien...
Biorąc pod uwagę język , jak mogę powiedzieć bezpośrednio, nie patrząc na reguły produkcji, że ten język nie jest regularny?L = {zanbndon}L.={zanbndon} L= \{a^n b^n c^n\} Mógłbym użyć lematu pompującego, ale niektórzy mówią tylko patrząc na gramatykę, że to nie jest normalne. Jak to jest...
W artykule Parsing Expressions by Recursive Descent autorstwa Theodore Norvell (1999) autor zaczyna od następującej gramatyki wyrażeń arytmetycznych: E --> E "+" E | E "-" E | "-" E | E "*" E | E "/" E | E "^" E | "(" E ")" | v co jest dość złe, ponieważ jest dwuznaczne i lewostronne. Zaczyna...
Kilka tygodni temu podjąłem egzaminy z teorii obliczeń i było to jedno z pytań: Załóżmy, że językL = { (zanbm)r∣ n , m , r ≥ 0 }L.={(zanbm)r∣n,m,r≥0}L=\{(a^nb^m)^r \mid n,m,r\ge 0\} Czy L jest regularny? Jeśli tak, podaj wyrażenie regularne lub automat. Po tym, jak krótko zapytałem go o...
Ostatnio zadałem pytanie na temat Math SE. Na razie brak odpowiedzi. To pytanie jest związane z tym pytaniem, ale bardziej technicznymi szczegółami w kierunku informatyki. Biorąc pod uwagę dwa DFA i gdzie zbiór stanów, alfabet wejściowy i funkcja przejścia i są takie same, stany początkowe i stany...
Szukam gramatyki kontekstowej opisującej następujący język: .L={ww∣w∈{a,b}∗,|w|≥1}L={ww∣w∈{a,b}∗,|w|≥1}L = \{ ww \mid w ∈ \{a,b\}^{\ast}, |w| ≥ 1\} Mam problem z tym, że żadne reguły, takie jak są dozwolone i dlatego nie mogę umieścić żadnego nieterminala wskazującego „środek” słowa. Czy jest...
Język formalny nad alfabetem jest podzbiorem , czyli zbiór słów nad tym alfabecie. Dwa formalne języki i są sobie równe, jeśli odpowiadające im zbiory są ponadto równe jako podzbiory . W teorii złożoności można używać języków, aby sformalizować pojęcie „problemu”. Można narzekać, że „ogólnie”...
Myślę o językach jednoargumentowych LkL.kL_k, gdzie LkL.kL_k jest zbiorem wszystkich słów, których długość jest sumą kkkkwadraty. Formalnie: Lk={an∣n=∑i=1kni2,ni∈N0(1≤i≤k)}L.k={zan∣n=∑ja=1knja2),nja∈N.0(1≤ja≤k)}L_k=\{a^n\mid n=\sum_{i=1}^k {n_i}^2,\;\;n_i\in\mathbb{N_0}\;(1\le i\le k)\} Łatwo to...
Zwykle widzę, że w strukturalnej reprezentacji operacyjnej semantyki dla pętli while stan programu nie zmienia się: (whileBdoS,σ)→(ifBthenS;(whileBdoS)elseSKIP,σ)(whileBdoS,σ)→(ifBthenS;(whileBdoS)elseSKIP,σ)(while \> B \> do \>S, \sigma) \rightarrow (if \>B \> then \>S; (while \> B \> do \>S) \>...
Zastanawiałem się ostatnio, co by się stało, gdybyśmy pozwolili gramatykom bezkontekstowym mieć nieskończoną liczbę reguł. Oczywiście, gdybyśmy zezwolili na arbitralne takie nieskończone zbiory reguł, każdy językLLL nad jakimś alfabetem ΣΣ\Sigma może być opisany przez CFG...